Welcome to this one-day workshop: A crash course on using machine learning methods effectively in practice

COURSE OUTLINE

  • 9:00 to 10:45: Supervised Learning (part 1)
  • 10:45 to 11:15: Break (might need a coffee)
  • 11:15 to 12:45: Supervised Learning (part 2)
  • 12:45 to 13:45: Lunch Break
  • 13h45 to 15:15: Unsupervised Learning (part 1)
  • 15:15 to 15:45: Break (might need another coffee)
  • 15:45 to 17:00: Unsupervised Learning (part 2)

Machine Learning (Introduction)

Definition

Tom Mitchell (1998): ``A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.’’

Stephen Boyd (2016): ``machine learning: extract information directly from historical data and extrapolate to achieve a task ( e.g. make predictions)’’

A first Example:

Consider the data from Breast Cancer Wisconsin (Diagnostic) (WBCD) dataset

  • Goal is to predict if a benign (Y = 0) or a malignant (Y = 1) lumps of a breast mass.

  • Historical data consists of a large number of patient records

  • 30 (=\(d\)) characteristics of individual cells of breast cancer

  • Use a machine learning algorithm that observes these data, produces a predictor

  • Predictor takes as input 30 values, returns a single Boolean prediction (0 or 1)

  • This is a classifier, since we are predicting an outcome that takes only two values

  • Evaluate model by its error rate on a separate test set of data, not used to develop the model

  • A probabilistic model returns a probability that the patient has a malignant lump, not just a Boolean

Sigmoid/Logistic model in action

  • We will run the sigmoid model using generalized linear model framework

  • Keep in mind sigmoid model is a logistic model

  • Lets run a model with one feature and a model with 10 features

load("Breast_cancer.RData")
library(dplyr)

Attaching package: ‘dplyr’

The following objects are masked from ‘package:stats’:

    filter, lag

The following objects are masked from ‘package:base’:

    intersect, setdiff, setequal, union
head(Breast_cancer_data[,c(1:6)])
data <- Breast_cancer_data
dim(data)
[1] 569  32
data <- data %>% mutate(diagnosis_0_1 = ifelse(diagnosis == "M", 1, 0))
var <- c(1,2,5,6,9,10,11,12,15,16,25,31)
data <- data[,-c(1,2)]
data <- data[,var]
colnames(data)
 [1] "radius_mean"            "texture_mean"           "smoothness_mean"       
 [4] "compactness_mean"       "symmetry_mean"          "fractal_dimension_mean"
 [7] "radius_se"              "texture_se"             "smoothness_se"         
[10] "compactness_se"         "smoothness_worst"       "diagnosis_0_1"         
library(ROCR)
library(caret)
Loading required package: ggplot2
Loading required package: lattice
set.seed(101)
training <- createDataPartition(data$diagnosis_0_1, p=0.8, list=FALSE)
train <- data[ training, ] #--> training data 
test <- data[ -training, ] #--> test data
trainfull <- train[,-c(1,2)]
uni.model <- glm(diagnosis_0_1~smoothness_worst,family=binomial,data=trainfull)
full.model <- glm(diagnosis_0_1~.,family=binomial,data=trainfull)
glm.fit: fitted probabilities numerically 0 or 1 occurred
summary(full.model)$coef
                          Estimate  Std. Error   z value     Pr(>|z|)
(Intercept)               6.341524   3.9417679  1.608802 1.076597e-01
smoothness_mean        -205.038026  51.1673877 -4.007201 6.144247e-05
compactness_mean        107.058369  19.8272716  5.399551 6.680780e-08
symmetry_mean            20.622891  14.0976782  1.462857 1.435064e-01
fractal_dimension_mean -478.435425  96.7456145 -4.945293 7.602936e-07
radius_se                18.153664   3.2350594  5.611539 2.005345e-08
texture_se                1.501148   0.7130725  2.105183 3.527536e-02
smoothness_se          -741.412778 179.0867319 -4.139965 3.473590e-05
compactness_se          -79.855639  27.4671773 -2.907311 3.645500e-03
smoothness_worst        195.309199  33.1556122  5.890683 3.846028e-09
  • We can now fornew patients give a prediction (probability value)
new.patients <- test
new.patients
p.full = predict(full.model, new.patients, type="response")
p.full[1:10]
         29          35          36          41          45          48          61 
0.999963726 0.990044782 0.999992477 0.033481026 0.868105685 0.921966302 0.002620119 
         63          66          68 
0.999929529 0.984120111 0.004692286 
  • We can also use the model as a classifier
my.classifier <- function(model,patient,threshold=0.5)  ifelse(predict(model, patient, type="response")>threshold,1,0)
my.classifier(full.model,new.patients[1:10,])
  • Confusion matrix

  • Performance measure

\[\begin{equation} \label{eq:acc-def} \text{Accuracy} = \frac{\text{TP} +\text{TN}}{n_{\text{test}}}, \end{equation}\]

which can be misleading for unbalanced data (especially rare event)

  • More robust measures are sensitivity (called recall) and specificity
pred.full <- my.classifier(full.model,test)
res.full <- confusionMatrix(as.factor(pred.full),as.factor(test$diagnosis_0_1),positive="1") 
table(pred.full,test$diagnosis_0_1)
         
pred.full  0  1
        0 70  5
        1  3 35
res.full$table
          Reference
Prediction  0  1
         0 70  5
         1  3 35
res.full$overall[1]
 Accuracy 
0.9292035 
res.full$byClass[c(1,2,5,6)]
Sensitivity Specificity   Precision      Recall 
  0.8750000   0.9589041   0.9210526   0.8750000 
pred.uni <- my.classifier(uni.model,test)
res.uni <- confusionMatrix(as.factor(pred.uni),as.factor(test$diagnosis_0_1),positive="1") 
res.uni$table
          Reference
Prediction  0  1
         0 66 24
         1  7 16
res.uni$overall[1]
 Accuracy 
0.7256637 
res.uni$byClass[c(1,2,5,6)]
Sensitivity Specificity   Precision      Recall 
  0.4000000   0.9041096   0.6956522   0.4000000 
  • A popular way to average precision and recall is by considering the harmonic mean of the two values.

  • This is called the F\(_1\) score :

\[\begin{equation} \label{eq:f1-score} F_1 = \frac{2}{\frac{1}{\text{Precision}} + \frac{1}{\text{Recall}}} = 2 \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}. \end{equation}\]

res.uni$byClass[7]
       F1 
0.5079365 
res.full$byClass[7]
       F1 
0.8974359 
  • Be aware that classifier based on threshold alters confusion matrix

  • Receiver Operating Characteristic (ROC) curve:


pr_full = prediction(pred.full, test$diagnosis_0_1)
perf_full = performance(pr_full, measure = "tpr", x.measure = "fpr")

pr_uni = prediction(pred.uni, test$diagnosis_0_1)
perf_uni = performance(pr_uni, measure = "tpr", x.measure = "fpr")


auc1 = performance(pr_full, measure = "auc")
auc1 = auc1@y.values[[1]]
auc2 = performance(pr_uni, measure = "auc")
auc2 = auc2@y.values[[1]]
print(paste("AUC full test", signif(auc1,digits=4)))
[1] "AUC full test 0.917"
print(paste("AUC uni test", signif(auc2,digits=4)))
[1] "AUC uni test 0.6521"
library(ROCit)
r1=rocit(predict(uni.model, test), test$diagnosis_0_1, method = "bin")
r3=rocit(predict(full.model, test), test$diagnosis_0_1, method = "bin")



plot(r1$TPR~r1$FPR, type = "l", xlab = "False Positive Rate", lwd = 2,
     ylab = "Sensitivity", col= "gold4",cex.lab=2,cex.axis = 2)
grid()
lines(r3$TPR~r3$FPR, lwd = 2, col = "orange")
segments(0,0,1,1, col = "2", lwd = 2)
segments(0,0,0,1, col = "darkgreen", lwd = 2)
segments(1,1,0,1, col = "darkgreen", lwd = 2)

legend("bottomright", c("Perfectly Separable", 
                        "Univariate", "Full model", "Chance Line"), cex=2,
       lwd = 2, col = c("darkgreen", "gold4",
                        "orange", "red"), bty = "n")

Machine learning model taxonomy

  • supervised versus unsupervised models

  • supervised learning models predict something, given some other things

    • called a prediction model
    • called regression when we predict a real scalar or vector value
    • called classification when we predict a value from a finite set such as True; False
  • unsupervised learning models just create a model of the data

    • sometimes called a data model
    • Dimension reduction
    • Find pattern in the data

Data: Seen, Unseen, Training, Testing

  • Distinguish between seen data and unseen data.

  • Seen data is available for learning, namely for training of models, model selection, parameter tuning, and testing of models.

  • Unseen data is essentially unlimited. All data from the real world that is not available while learning takes place but is later available when the model is used. This can be data from the future, or data that was not collected or labelled with the seen data.

  • Machine learning works well if nature of the seen data is similar to unseen data.

  • Common practice is to split the seen data into training data and testing data (also named hold out set).

  • Training data is used for learning.

  • Testing data for mimicking a scenario of unseen data.

  • To do recalibrate, adjust, or tune models on the training set while testing repeatedly on the test set.

  • Performs an additional split of the training data by removing a chunk out of the training data and calling it the validation set.

  • Statistical approaches generally use all available data and evaluate quality of models using selection criterion as Akaike information criterion (AIC) or *Bayesian information criterion (BIC).

  • Sometimes instead of using a validation set we can do k-fold cross validation

Data Preprocessing

  • standardization of the data: subtraction of the mean of each feature and division by the standard deviation of the feature.

  • sample mean and sample standard deviation

\[\begin{equation} \label{eq:stats-mean-var} \overline{x}_i = \frac{1}{n} \sum_{j=1}^n x_i^{(j)}, \qquad s^2_i = \frac{1}{n} \sum_{j=1}^n (x_i^{(j)} - \overline{x}_i)^2. \end{equation}\]

  • standardization

\[\begin{equation} \label{eq:ref-stand-z} z^{(j)}_i = \frac{x^{(j)}_i - \overline{x}_i}{s_i} \qquad \text{for} \qquad j=1,\ldots,n. \end{equation}\]

  • For feature \(i\), \(z_i^{(1)}, \ldots,z_i^{(n)}\), has a sample mean of exactly \(0\) and a sample standard deviation of exactly \(1\).

  • Such standardization is useful as it places the dynamic range of the model inputs on a uniform scale and thus improves the numerical stability of algorithms.

  • We will discuss how such standardization can also help optimization performance.

Learning \(\simeq\) Optimization

  • Learning activity involves optimization either explicitly or implicitly.

  • This is because learning is the process of seeking model parameters that are best for some given task.

  • Optimize some performance measure that quantifies how good the model at hand performs.

  • Example, use mean square error criterion for regression problems

  • In other cases, a loss function is used such that minimization of the loss function is a proxy for minimization of the actual performance measures that are of interest.

  • Example, for classification problems we aim to get the most accurate classifier but optimization is typically not carried out directly on the accuracy measure but rather on a loss function such as the mean square error, or cross entropy

Supervised learning

  • More common form of machine learning

  • Data is comprised of the features (independent variables) \(X\) and the labels (dependent variables, response variables) \(Y\).

  • Regression problem when the variable to be predicted \(Y\) is a continuous or numerical variable

  • Classification problem, in cases where \(Y\) comes from some finite set of label values.

Basics: linear models

  • Start simple with an example: Housing data

  • univariate example: \(x\) is the average number of rooms per dwelling and \(y\) is the median value of owner-occupied homes in thousands of dollars.

  • A regression model \(y = f_\theta(x)\) attempts to predict the median house price as a function of the average number of rooms.

\[\begin{equation} \label{eq:simple-linear-reg} y = \beta_0 + \beta_1 x + \epsilon, \end{equation}\]

library(MASS)

Attaching package: ‘MASS’

The following object is masked from ‘package:dplyr’:

    select
library(tidyverse)
Registered S3 methods overwritten by 'dbplyr':
  method         from
  print.tbl_lazy     
  print.tbl_sql      
── Attaching packages ────────────────────────────────────────────── tidyverse 1.3.1 ──
✔ tibble  3.1.7     ✔ purrr   0.3.4
✔ tidyr   1.2.0     ✔ stringr 1.4.0
✔ readr   2.1.2     ✔ forcats 0.5.1
── Conflicts ───────────────────────────────────────────────── tidyverse_conflicts() ──
✖ dplyr::filter() masks stats::filter()
✖ dplyr::lag()    masks stats::lag()
✖ purrr::lift()   masks caret::lift()
✖ MASS::select()  masks dplyr::select()
data("Boston", package = "MASS")
ind <- which(Boston$medv==50)
Boston.s <- Boston[-ind,]
train.data  <- Boston.s

model1 <- lm(medv~rm,data=train.data)


p1 <- ggplot(train.data, aes(rm, medv)) +
  geom_point(size=2) + stat_smooth(method = "lm", col = "red") +
  xlab('Average number of rooms per dwelling (rm)') + ylab('House prices in $1000 (medv)')+
  theme(legend.position = 'bottom')  + theme_bw()
p1 + theme(axis.text = element_text(size = 10))+ theme(axis.title = element_text(size = 10))   

  • Not everything is linear: Polynomial model

\[\begin{equation} \label{eq:poly-2-reg} y = \beta_0 + \beta_1 x + \beta_2 x^2 + \epsilon. \end{equation}\]

model.lm <- lm(medv~lstat,data=train.data)
model.quad <- lm(medv~lstat+I(lstat^2),data=train.data)

p2 <- ggplot(train.data, aes(lstat, medv) ) +
  geom_point(size=2) +
  stat_smooth(method = lm, formula = y ~ poly(x, 2, raw = TRUE))+
  stat_smooth(method = lm, formula = y ~ x,col='red')+
  xlab('Lower status of the population in % (lstat)') + ylab('House prices in $1000 (medv)')+
  theme(legend.position = 'bottom')  + theme_bw()
p2 + theme(axis.text = element_text(size = 10))+ theme(axis.title = element_text(size = 10))   

Learning the linear model

  • Consider a training dataset \(\mathcal{D}=\{(x^{(1)},y^{(1)}),\ldots,(x^{(n)},y^{(n})\}\) composed of a collection of \(n\) samples.

  • Design matrix \(X\) for the features, and the corresponding output response vector \(y\), via,

\[\begin{equation} \label{eq:design} X=\begin{bmatrix} \vert & \vert & &\vert \\ 1 &x_{(1)} &\dots &x_{(p)} \\ \vert & \vert & & \vert \end{bmatrix} \quad \textrm{with} \quad x_{(i)}=\begin{bmatrix} x_i^{(1)} \\ \vdots \\ x_i^{(n)} \end{bmatrix}, \quad \textrm{and} \quad y= \begin{bmatrix} y^{(1)} \\ %y^{(2)} \\ \vdots \\ y^{(n)} \end{bmatrix} . \end{equation}\]

  • Linear model for all the samples of the training set via \[ y=X\theta+ \epsilon, \] with \(\epsilon=(\epsilon_1,\dots,\epsilon_n)\)

  • Define the predicted output vector of the model for the input training data via, \[ \hat{y}=X\widehat{\theta}, \qquad \text{where} \qquad \hat{y} = \begin{bmatrix} \hat{y}^{(1)} \\ %y^{(2)} \\ \vdots \\ \hat{y}^{(n)} \end{bmatrix}. %(\hat{y}^{(1)},\ldots,\hat{y}^{(n)}). \]

  • A suitable learned value for \(\widehat{\theta}\) will yield \(\hat{y}\approx y\).

  • This closeness is captured via a loss function: \[\begin{equation} \label{eq:general-additive-loss} C(\theta \,; \, \mathcal D)=\frac{1}{n}\sum_{i=1}^nC_i(\theta) \end{equation}\] where \(C_i(\theta):=C_i(\theta \, ; \, y^{(i)}, \hat{y}^{(i)})\) is the loss for the \(i\)-th data sample. Specifically \(\widehat{\theta}\) is typically chosen so that the loss function is minimal at the point \(\theta = \widehat{\theta}\).

  • For the linear model: square loss function also called quadratic loss where the loss for each data sample is \[\begin{equation} \label{eq:quadratic-loss-one-obs} C_i(\theta)=({y}^{(i)} - \hat{y}^{(i)})^2. \end{equation}\]

  • Loss for the entire training data can be represented in terms of the \(L_2\) norm \(\|\cdot \|\) of the corresponding error vector, \[ C(\theta;\mathcal D) = \frac{1}{n}\sum_{i=1}^n({y}^{(i)} - \hat{y}^{(i)})^2 = \frac{1}{n}\|{y}-\hat{y}\|^2 \]

  • Optimize:

\[\begin{equation} \label{eq:least-squares-opt} \hat{\theta} =\textrm{argmin}_{\theta\in \Re^d} \frac{1}{n}{\| y - X\theta\|^2} = \textrm{argmin}_{\theta\in \Re^d}{\|y - X\theta\|}^2. \end{equation}\]

  • The least squares solution can be easily derived by first computing the gradient of \(||X\theta-y||^2\) with respect to \(\theta\) \[\begin{equation} \label{eq:gradLS} \begin{aligned} \frac{\partial \| y - X\theta\|^2}{\partial \theta}&=-2X^\top y+2X^\top X\theta. \end{aligned} \end{equation}\]

  • Setting the gradient to 0 we get

\[\begin{equation} \label{eq:normal} X^\top X\theta=X^\top y, \end{equation}\]

  • Unique solution when the \(d\times d\) matrix \(X^\top X\), also known as the Gram matrix of \(X\), is invertible.

  • In this case: \(\hat{\theta}=(X^\top X)^{-1}X^\top y\), or, by setting \(X^{\dagger} = (X^\top X)^{-1}X^\top\), we have,

\[\begin{equation} \label{eq:closedform} \hat{\theta}=X^{\dagger} y, \end{equation}\]

where \(X^{\dagger}\) is Moore-Penrose pseudo-inverse of \(X\).

  • Using the SVD (more details latter) we can represent the Moore-Penrose pseudo-inverse as

\[\begin{equation} \label{eq:svd-based-mppi} X^{\dagger} = V \Delta^+U^\top, \end{equation}\] where \(\Delta^+\) contains the reciprocals of the non-zero (diagonal) elements of \(\Delta\), and has \(0\) values elsewhere.

  • This SVD-based representation holds both if \(X^\top X\) is singular

  • For high dimensional data \(p>>n\) design matrix \(X\) is never full rank.

A practice of linear model for classification

  • One of the most common datasets is the MNIST Digits dataset. It is composed of monochrome digits of \(28\times 28\) pixels and labels indicating each digit.

We use R to extract the information from these files.

file_training_set_image <- "train-images.idx3-ubyte"
file_training_set_label <- "train-labels.idx1-ubyte"
file_test_set_image <- "t10k-images.idx3-ubyte"
file_test_set_label <- "t10k-labels.idx1-ubyte"

extract_images <- function(file, nbimages = NULL) {
    if (is.null(nbimages)) {
        # We extract all images
        nbimages <- as.numeric(paste("0x", paste(readBin(file, "raw", n = 8)[5:8], collapse = ""), sep = ""))
    }
    nbrows <- as.numeric(paste("0x", paste(readBin(file, "raw", n = 12)[9:12], collapse = ""), sep = ""))
    nbcols <- as.numeric(paste("0x", paste(readBin(file, "raw", n = 16)[13:16], collapse = ""), sep = ""))
    raw <- readBin(file, "raw", n = nbimages * nbrows * nbcols + 16)[-(1:16)]
    return(array(as.numeric(paste("0x", raw, sep = "")), dim = c(nbcols, nbrows, nbimages)))
}

extract_labels <- function(file) {
    nbitem <- as.numeric(paste("0x", paste(readBin(file, "raw", n = 8)[5:8], collapse = ""), sep = ""))
    raw <- readBin(file, "raw", n = nbitem + 8)[-(1:8)]
    return(as.numeric(paste("0x", raw, sep = "")))
}

images_training_set <- extract_images(file_training_set_image, 60000)
images_test_set <- extract_images(file_test_set_image, 10000)
labels_training_set <- extract_labels(file_training_set_label)
labels_test_set <- extract_labels(file_test_set_label)

labels_training_set[1:10]
 [1] 5 0 4 1 9 2 1 3 1 4
# par(ask = TRUE)
par(mfrow = c(2, 2))
for (i in 1:4) image(as.matrix(rev(as.data.frame(images_training_set[, , i]))), col = gray((255:0)/256))

  • Each training input \(\mathbf{x}\) is a \(28\times 28 = 784\)-dimensional vector. Each entry in the vector represents the grey value for a single pixel in the image.

  • We’ll denote the corresponding desired output by \(\mathbf{y} = y(\mathbf{x})\), where \(\mathbf{y}\) is a 10-dimensional vector. For example, if a particular training image, \(\mathbf{x}\), depicts a 6, then \(y(\mathbf{x})=(0,0,0,0,0,0,1,0,0,0)\top\) is the desired output from the network.

  • We consider each image as a vector and obtain different least squares estimators for each type of digit. For digit \(\ell\in{0,\ldots,9}\) we collect all the training data vectors, with \(y_i=\ell\). Then for each such \(i\), we set \(y_i = +1\) and for all other \(i\) with \(y_i\neq \ell\), we set \(y_i = −1\).

  • This labels our data as classifying yes digit vs. not digit. Call this vector of −1 and +1 values \(y^{(\ell)}\) for every digit \(\ell\).

  • We then compute, \[\beta^{(\ell)}=(X^TX)^{-1}X^\top y^{\ell}\ \ \ \ \ \textrm{for} \ \ \ \ell=0,\ldots,9\] where \(X\) is the \(60,000\times 784\) design matrix associated with the \(60,000\) images.

Now for every image \(i\), the inner product \(\beta^{(\ell)}.\mathbf{x}^\top_i\) yields an estimate of how likely this image is of the digit \(\ell\). A very high value indicated a high likelihood and a low value is a low likelihood. We then classify an arbitrary image \(\tilde{\mathbf x}\) by

\[\begin{eqnarray} \hat{y}(\tilde{x}) = \textrm{arg max } \beta^{(\ell)}.\tilde{x}^\top \ \ \ \ \ \ \ (1) \end{eqnarray}\]

  • Observe that during the training, this classifier only requires calculating \((X^TX)^{-1}X^T\) once. It then only needs to remember 10 vectors \(\beta_0,\ldots,\beta_9\). Then based on these 10 vectors, a decision rule is very simple to execute in (1).

  • Create Design matrix and outcome responses

vectorized_result <- function(j) {
  e <- as.matrix(rep(0, 10))
  e[j + 1] <- 1
  return(e)
}

Xtrain <- matrix(0,nrow=60000,ncol=784)
Ytrain <- matrix(0,nrow=60000,ncol=10)
for (i in 1:60000) {
  Xtrain[i,] <- as.vector(images_training_set[,,i]) / 256
  Ytrain[i,] <- t(vectorized_result(labels_training_set[i]))
}
Ytrain[which(Ytrain==0)] <- -1

Xtest <- matrix(0,nrow=10000,ncol=784)
Ytest <- matrix(0,nrow=10000,ncol=10)
for (i in 1:10000) {
  Xtest[i,] <- as.vector(images_test_set[,,i]) / 256
  Ytest[i,] <- t(vectorized_result(labels_test_set[i]))
}
  • Compute the key element \((X^TX)^{-1}X^T\). As \((X^TX)\) is singular, we use the Moore-Penrose generalized inverse matrix of \(X\) through the function from the R package:
library(MASS)
mat <- ginv(Xtrain)
  • Estimate the 10 linear classifier models
model <- matrix(0,nrow=784,ncol=10)
for(i in 1:10){
model[,i] <- mat%*%matrix(Ytrain[,i],ncol=1)  
}
  • Create the prediction function for the linear classifier

pred.model <- function(x,Xtest=Xtest){sum(x*Xtest)}

linear.class <- function(model,Xtest){
  res <- apply(model,MARGIN=2,FUN=pred.model,Xtest=Xtest)
  pred <- which.max(res)-1
  return(pred)
}
  • Performance on the test data
result <- 0
res <- rep(0,10000)
for (i in 1:10000){
Xtest1 <- (as.vector(images_test_set[,,i]) / 256)
resi <- linear.class(model,Xtest=Xtest1)
res[i] <- resi
if(abs(resi-labels_test_set[i])<0.5) result <- result +1
}
accuracy <- result/10000
accuracy
[1] 0.8534
  • Confusion Matrix
library(caret)
caret::confusionMatrix(factor(res),factor(labels_test_set))$table
          Reference
Prediction    0    1    2    3    4    5    6    7    8    9
         0  942    0   17    4    0   20   17    5   17   18
         1    0 1107   56   15   23   17    9   38   54   10
         2    2    2  809   26    6    2   10   18    9    2
         3    2    2   28  887    3   84    0    8   32   15
         4    1    1   16    2  872   19   21   20   27   72
         5    7    1    0   14    5  624   20    0   42    1
         6   15    5   42    9   10   22  872    1   15    1
         7    2    2   21   21    2   13    0  877   12   76
         8    7   15   39   21   13   69    9    3  743   13
         9    2    0    4   11   48   22    0   58   23  801
  • We have used the one vs.\ all (also known as one vs.\ rest) strategy using Binary classification for multi-class classification problem (see later)

  • Second option: one vs. one strategy. We have \(K(K-1)/2\) binary classifiers denoted \({f}_{{\theta}_{i,j}}(x)\) for all \(i,j = 1,\ldots,K\) such that \(i \neq j\). Here the \((i,j)th\) classifier discriminates between the label being of index \(i\) or index \(j\)

  • The one vs. all or one vs. one strategies carry out prediction via,

\[ \widehat{\cal Y} = \begin{cases} \textrm{argmax}_{i=1,\ldots,K} {f}_{{\theta}_i}(x) & \qquad \text{in case of one vs. all}, \\ \textrm{argmax}_{i=1,\ldots,K} \sum_{j \neq i} \text{sign}\big( {f}_{{\theta}_{i,j}}(x) \big)& \qquad \text{in case of one vs. one}. \\ \end{cases} \]

  • The idea of the one vs. one classifier is to pick the label \(i\) that when compared to the other \(K-1\) labels, was chosen most often.

Model Choice, Under-fitting, and Over-fitting

  • Tradeoffs of model complexity using linear models with polynomial features

\[\begin{equation} \label{poly} y = \beta_0 + \beta_1 x + \beta_2 x^2 + \ldots + \beta_k x^k+ \epsilon \end{equation}\]

  • \(\mathcal{M}_k\) means polynomial model of order \(k\)

  • Hence \(\mathcal{M}_0\) is the constant model, \(\mathcal{M}_1\) is the simple linear model, \(\mathcal{M}_2\) is the quadratic model, and so on.

  • Model complexity corresponds to the degree of the polynomial model.

  • \(\mathcal{D}_{\text{train}}\) of size \(n_{\text{train}}=10\).

  • Let try different model \(\mathcal{M}_k\).
load("data-poly.Rdata")
y <- mydata$y
x <- mydata$x
model0 <- glm(y~1)
model1 <- glm(y~poly(x,1))
model2 <- glm(y~poly(x,2))
model3 <- glm(y~poly(x,3))
model4 <- glm(y~poly(x,4))
model5 <- glm(y~poly(x,5))
model6 <- glm(y~poly(x,6))
model7 <- glm(y~poly(x,7))
model8 <- glm(y~poly(x,8))
model9 <- glm(y~poly(x,9))

# Much better
model.list <- vector("list", length = 10)
model.list[[1]] <- glm(y~1)
for (i in 1:9){
  formula <- as.formula(paste("y ~ poly(x,",i,")",sep=""))
  model.list[[i+1]] <- glm(formula) 
}



my.formula <- y ~ 1
p0 <- ggplot(mydata, aes(x, y)) + 
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, 
              formula = my.formula, 
              colour = "red")+
  labs(title=element_text("Polynomial fit with k=0"))+
  theme(legend.position = "none") + theme_bw()


my.formula <- y ~ poly(x, 1, raw = TRUE)

p1 <- ggplot(mydata, aes(x, y)) + 
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, 
              formula = my.formula, 
              colour = "red")+
  labs(title=element_text("Polynomial fit with k=1"))+
  theme(legend.position = "none") + theme_bw()

my.formula <- y ~ poly(x, 3, raw = TRUE)

p3 <- ggplot(mydata, aes(x, y)) + 
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, 
              formula = my.formula, 
              colour = "red")+
  labs(title=element_text("Polynomial fit with k=3"))+
  theme(legend.position = "none")+ theme_bw()


my.formula <- y ~ poly(x, 9, raw = TRUE)


p9 <- ggplot(mydata,aes(x, y=y)) + 
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, 
              formula = my.formula, 
              colour = "red")+
  labs(title=element_text("Polynomial fit with k=9"))+
  theme(legend.position = "none") + theme_bw()

library(ggpubr)
ggarrange(p0,p1,p3,p9,ncol = 2, nrow = 2)

  • It is obvious that as \(k\) increases training fit improves.

  • Evaluate the performance of the model using a performance measure \({\cal P}\)

\[\begin{equation} \label{eq:e-train-train} {E}_{\text{train}} = \frac{1}{n_{\text{train}}}\sum_{(x,y) \in \mathcal{D}_{\text{train}}} {\cal P} \big(\widehat{y}(x \, ; \, \mathcal{D}{\text{train}}),\, y\big), \end{equation}\]

  • Here natural to use \({\cal P}(\big(\widehat{y}(x \, ; \, \mathcal{D}_{\text{train}}),\, y\big))=(\widehat{y}-y)^2\)
RMSE <- function(model,dataXY){
  pred <- predict.glm(model,newdata=data.frame(x=dataXY$X))
  RMSE <- mean((pred-dataXY$Y)**2)
  return(RMSE)
}

data.train <- data.frame(X=x,Y=y)

RMSE.result <- matrix(NA,nrow=10,ncol=2)
for(i in 1:10){
  model <- model.list[[i]]
  RMSE.result[i,] <- c(i-1,RMSE(model,data.train))
}

data.result <- as.data.frame(RMSE.result)
colnames(data.result) <- c("M","Train")
mydata <- data.frame(Model=data.result$M,Performance=data.result$Train,Group=rep("Train",each=10),color=rep("red",each=10))



linetype = c('solid', 'solid')
LegendTitle = ""
p <- ggplot(mydata, aes(Model,Performance, group = Group,color=color))+
  geom_line(aes(group = Group,color=color))+#,"red")) +
  scale_color_identity(labels = c(blue = "blue",red = "red"))+
  #scale_linetype_manual(name = LegendTitle, values = linetype) +
  scale_x_continuous(name="Model (k)",breaks=0:9,labels=0:9)+
  scale_y_continuous(name="Mean Square Error")+
  theme_bw() +
  annotate(geom="text", x=7.5, y=1, label="E_train ",color="red")+
  annotate("segment", x = 6.6, xend = 7, y = 1, yend = 1,
         colour = "red")
p

  • It is obvious that as \(k\) increases training fit improves.

  • Hypothetical example: we know the underlying process with probability law \(P(x,y)\) used for purposes of simulation of synthetic data

  • We may sample as many \((x^\star,y^\star)\) pairs as we wish, to obtain the performance measure for unseen data \(E_{\text{unseen}}\).

  • \(10,000\) repetitions for each \(k\), each time with the fixed model based on our single available dataset.

set.seed(1123)
testx <- seq(0,1,length=10000)
testy <- sin(2*pi*testx)-cos(2*pi*testx)+rnorm(10000,0,0.2)
data.test <- data.frame(X=testx,Y=testy)


RMSE.result <- matrix(NA,nrow=10,ncol=3)
for(i in 1:10){
  model <- model.list[[i]]
  RMSE.result[i,] <- c(i-1,RMSE(model,data.train),RMSE(model,data.test))
}


colnames(RMSE.result) <- c("M","Train","Test")
data.result <- as.data.frame(RMSE.result)
colnames(RMSE.result) <- c("M","Train","Test")
mydata <- data.frame(Model=rep(data.result$M,2),Performance=c(data.result$Train,data.result$Test),Group=rep(c("Train","Production"),each=10),color=rep(c("red","black"),each=10))

linetype = c('solid', 'solid')
LegendTitle = ""
p <- ggplot(mydata, aes(Model,Performance, group = Group,color=color))+
  geom_line(aes(group = Group,color=color))+#,"red")) +
  scale_color_identity(labels = c(blue = "blue",red = "red"))+
  scale_x_continuous(name="Model (k)",breaks=0:9,labels=0:9)+
  scale_y_continuous(name="Mean Square Error")+
  theme_bw() +
  annotate(geom="text", x=7.5, y=1, label="E_train", parse=TRUE
             ,color="red")+
  annotate("segment", x = 6.6, xend = 7, y = 1, yend = 1,
         colour = "red")+
  annotate(geom="text", x=7.6, y=0.95, label="E_unseen", parse=TRUE
           ,color="black")+
annotate("segment", x = 6.6, xend = 7, y = 0.95, yend = 0.95,
         colour = "black")
p

  • It clear that when \(k=9\) or \(k=8\) there is over-fitting and when \(k=0,1,2\) there is under-fitting.

  • In practice plots cannot be produced because we do not know \(P(x,y)\). Instead one can resort to estimates based on cross validation to obtain curves similar to the black curve

  • Behaviour of expected generalization performance and expected training performance

Bias and Variance Decomposition

  • bias and variance tradeoff.

  • Special case of the square error performance function \({\cal P}(\hat{y}, y) = (\hat{y} - y)^2\) and a specifically assumed underlying random reality

\[\begin{equation} \label{eq:process-real} y= f(x) + \epsilon, \quad \text{with} \quad \textrm{E}[\epsilon]=0, \quad \text{and }\epsilon\text{ is independent of }x. \end{equation}\]

  • \(x\) a vector of features and \(y\) a scalar real valued label.

  • For some unseen feature vector \(x^\star\), the predictor trained on data \(\mathcal D\) is \(\widehat{y}(x^\star \, ;\, \mathcal D)\), which we also denote via \(\hat{f}(x^\star \, ; \, \mathcal D)\)

  • The expected generalization performance

\[\begin{equation} \label{eq:e-unseen-on-way} \widetilde{E}_{\text{unseen}} ={\mathbb E}_{\mathcal D, x^\star, \epsilon} \Big[ \big(\hat{f}(x^\star;\mathcal D)-(f(x^\star)+\epsilon) \big)^2\Big]. \end{equation}\]

  • This can be expressed as a bias-variance-noise decomposition equation,

\[\begin{equation} \label{eq:biasVarTrad} \widetilde{E}_{\text{unseen}}=\underbrace{\left({\mathbb E}[\hat{f}(x^\star\, ; \, \mathcal D)]-{\mathbb E}[f(x^\star)]\right)^{2}}_{\text{Bias squared of~} \hat{f}(\cdot)} ~+~~ \underbrace{\text{Var} \big(\hat{f}(x^\star\, ; \, \mathcal D)\big)}_{\text{Variance of}~\hat{f}(\cdot)} ~~~+~ \underbrace{{\mathbb E}[\epsilon^2]}_{\text{Inherent Noise}}. \end{equation}\]

  • The model bias is a measure of how a typical model \(\hat{f}(\cdot \, ; \, \mathcal D)\) misspecifies the correct relationship \({f}(\cdot)\).

  • The model variance is a measure of the variability of the model class \(\hat{f}(\cdot\, ; \, \mathcal D)\).

  • Model classes with high model variance are often overfit (to the training data) and do not **{generalize (to unseen data) well.

  • For example in a classification setting you may compare the accuracy obtained on the training set to that obtained on a validation set. If there is a high discrepancy where the training accuracy is much higher than the validation accuracy, then there is probably a variance problem indicating that the model is overfitting.

Addition of Regularization Terms

  • Control model variance is to induce or force model parameters to remain within some confined subset of the parameter space.

  • This is called regularization.

  • A decreases in model variance may imply an increase of model bias.

  • A common way to keep model parameters at bay is to augment the optimization objective \(\min_{\theta} C(\theta \, ; \,\mathcal D)\) with an additional \(R_\lambda(\theta)\).

  • The revised objective is t \[\begin{equation} \label{eq:regularization} \min_{\theta} ~C(\theta \, ; \, \mathcal D) + R_\lambda(\theta). \end{equation}\]

  • \(R_\lambda(\theta)\) depends on a regularization parameter \(\lambda\)

  • This hyper-parameter allows us to optimize the bias and variance tradeoff.

  • A common general regularization technique called elastic net has regularization parameter \(\lambda = (\lambda_1, \lambda_2)\) and,

\[\begin{equation} \label{eq:e-net} R_\lambda(\theta) = \lambda_1 \| \theta \|_1 + \lambda_2 \| \theta\| ^2 \quad \text{with} \quad \|\theta\|_1 = \sum_{i=1}^{d} | \theta_i | ~~ \text{and} ~~ \|\theta\|^2 = \sum_{i=1}^{d} \theta_i^2, \end{equation}\]

  • With \(\lambda_1, \lambda_2 = 0\) the original objective is unmodified.

  • In contrast, as \(\lambda_1 \to \infty\) or \(\lambda_2 \to \infty\) the estimates \(\theta_i \to 0\) and any information in the data \(\mathcal D\) is fully ignored.

  • Particular cases of elastic net are the classic ridge regression: \(\lambda_1 = 0\)

  • For \(\lambda_2 = 0\) we have the LASSO (least absolute shrinkage and selection operator)

  • With LASSO, the penalty \(|| \theta ||_1\) allows the algorithm to remove variables from the model

  • Hence LASSO is very useful as a model selection technique.

  • The regularization parameter \(\lambda\) is a hyper-parameter that one would like to calibrate during learning.

load("Breast_cancer.RData")
library(glmnet)
data <- Breast_cancer_data
data <- data %>% mutate(diagnosis_0_1 = ifelse(diagnosis == "M", 1, 0))
library(caret)
set.seed(101)
training <- createDataPartition(data$diagnosis_0_1, p=0.8, list=FALSE)
train <- data[ training, ]
test <- data[ -training, ]
trainfull <- train[,-c(1,2)]
testfull <- data[ -training, -c(1,2)]
model.lasso <- glmnet(trainfull[,-31],trainfull[,31],family="binomial",alpha=1)
model.ridge <- glmnet(trainfull[,-31],trainfull[,31],family="binomial",alpha=0)
par(mfrow=c(2,2))
plot(model.ridge,xvar="lambda")
plot(model.lasso,xvar="lambda")
plot(model.ridge,xvar="dev")
plot(model.lasso,xvar="dev")

  • We pick a lambda
ind.lambda.r <- which.min(model.ridge$dev.ratio<0.8)
#model.ridge$beta[,ind.lambda.r]
ind.lambda.l <- which.min(model.lasso$dev.ratio<0.8)
#model.lasso$beta[,ind.lambda.l]
res <- cbind(model.ridge$beta[,ind.lambda.r],model.lasso$beta[,ind.lambda.l])
colnames(res) <- c("ridge","lasso")
res
                                ridge       lasso
radius_mean              7.594749e-02  0.00000000
texture_mean             5.975381e-02  0.00000000
perimeter_mean           1.089765e-02  0.00000000
area_mean                7.228806e-04  0.00000000
smoothness_mean          8.288914e+00  0.00000000
compactness_mean         1.841181e+00  0.00000000
concavity_mean           2.873464e+00  0.00000000
concave.points_mean      6.984665e+00 13.18732706
symmetry_mean            3.438559e+00  0.00000000
fractal_dimension_mean  -1.535919e+01  0.00000000
radius_se                9.001367e-01  1.01502088
texture_se              -1.638285e-02  0.00000000
perimeter_se             1.006807e-01  0.00000000
area_se                  5.020945e-03  0.00000000
smoothness_se           -1.333716e+01  0.00000000
compactness_se          -4.755243e+00  0.00000000
concavity_se            -5.804244e-01  0.00000000
concave.points_se        1.118136e+01  0.00000000
symmetry_se             -3.620015e+00  0.00000000
fractal_dimension_se    -5.602774e+01  0.00000000
radius_worst             6.523028e-02  0.38973127
texture_worst            4.997564e-02  0.09262034
perimeter_worst          9.048926e-03  0.00000000
area_worst               5.036682e-04  0.00000000
smoothness_worst         1.017587e+01  5.03527345
compactness_worst        9.392522e-01  0.00000000
concavity_worst          1.227223e+00  0.47407610
concave.points_worst     4.624727e+00 14.10470598
symmetry_worst           3.643479e+00  2.51759237
fractal_dimension_worst  4.145747e+00  0.00000000

Hyper-parameter Calibration and Cross Validation

  • WARNING: calibrating the model choice and the hyper-parameters while reusing the testing set for performance evaluation is bad practice !!!

  • For this reason it is common to further split the training data \(\mathcal D_{\text{train}}\)

  • \(\mathcal D_{\text{test}}\) is still reserved only for final performance evaluation before rolling out the model to production.

  • Two main approaches, the train-validate split approach and K-fold cross validation.

  • The train-validate split approach is common in situations where the total number of datapoints \(n\) is large.

  • The K-fold cross validation approach is useful when data is limited.

  • The train-validate split implies that the original data with \(n\) samples is first split to training and testing. Then the training data is further split into two subsets: the first is (confusingly) again called the training set and the latter is the validation set.

\[ \mathcal D = \mathcal D_{\text{train}} \cup \mathcal D_{\text{validate}} \cup \mathcal D_{\text{test}}, \quad \text{where the unions are of disjoint sets.} \]

  • For example, we use a 80-20 rule for both splits and assuming divisibility holds, then \(n_{\text{test}} = 0.2 \times n\), \(n_{\text{train}} = 0.64 \times n\) and \(n_{\text{validation}} = 0.16 \times n\).

  • Alternative approach is K-fold cross validation.

  • Practice for lasso and ridge models
## Example Lasso and ridge regression 
## Breast cancer 
### A practice on Breast Cancer Data
model.lasso <- cv.glmnet(as.matrix(trainfull[,-31]),trainfull[,31],family="binomial",alpha=1,type.measure = "class")
model.ridge <- cv.glmnet(as.matrix(trainfull[,-31]),trainfull[,31],family="binomial",alpha=0,type.measure = "class")
plot(model.lasso)

  • Evaluate best model on test data
res.l <- predict(model.lasso,s = "lambda.min",newx=as.matrix(testfull[,-31]),type="response")
classifier.l <- ifelse(res.l>0.5,"1","0")
table(classifier.l,testfull[,31])
            
classifier.l  0  1
           0 73  2
           1  0 38
result.lasso <- caret::confusionMatrix(factor(classifier.l),factor(testfull[,31]),positive="1")
result.lasso$table
          Reference
Prediction  0  1
         0 73  2
         1  0 38
result.lasso$overall[1]
 Accuracy 
0.9823009 
result.lasso$byClass[c(1,2,5,6)]
Sensitivity Specificity   Precision      Recall 
       0.95        1.00        1.00        0.95 

Multi-class Problems with Softmax

  • multinomial regression model, softmax regression, softmax logistic regression, multinomial logistic regression, multi-class logistic regression generalize sigmoid (logistic model) from binary response case to the case of \(K>2\) classes.

  • \(\mathcal D=\left\{(x^{(1)},y^{(1)}),\ldots,(x^{(n)},y^{(n)})\right\}\) with each label \(y^{(j)}\) is one of \(K\) class values \(\{1,\ldots,K\}\).

  • Aim: predict class probability vectors, or if used for classification, to predict a class in a multi-class setting.

  • The predicted response is the probability vector \[\begin{equation} \label{eq:bold-phi-phi-x} \boldsymbol{\phi}(x)=\big(\phi_1(x), \ldots, \phi_K(x) \big), \end{equation}\]

where \[\begin{equation} \label{eq:phi-mult-case} \phi_k(x) = P(Y = k ~|~ X=x) \quad \text{for} \quad k=1,\ldots,K. \end{equation}\]

  • Statistical parameterization \[\begin{equation} \label{eq:stat-param1} \phi_k(x)=\frac{e^{b_k+w_{(k)}^\top x}}{1+\sum_{j=1}^{K-1} e^{b_j+w_{(j)}^\top x}} \qquad \text{for} \qquad k=1,\ldots,K-1, \end{equation}\]

and further, \[\begin{equation} \label{eq:stat-param2} \phi_K(x)=1-\sum_{j=1}^{K-1}\phi_j(x). \end{equation}\]

  • regression parameter:

\[\begin{equation} \label{eq:star-rep-min-mult-model-theta} \theta=(b_1,\ldots,b_{K-1},w_{(1)},\ldots,w_{(K-1)})\in \underbrace{\Re\times\ldots \times\Re}_{K-1~\text{times}} \times \underbrace{\Re^p\times\ldots\times\Re^p}_{K-1~\text{times}} := \Theta, \end{equation}\]

  • Softmax Function defines for \(z = (z_1,\ldots,z_K) \in \Re^K\):

\[\begin{equation} \label{eq:softmax-in-mult} S_{\text{softmax}}(z) = \frac{1}{\sum_{i=1}^{K} e^{z_i}} \begin{bmatrix} e^{z_1} \\ \vdots\\ e^{z_{K}}\\ \end{bmatrix}. \end{equation}\]

  • For any vector \(z \in \Re^K\), the result of \(S_{\text{softmax}}(z)\) is a probability vector

  • Now apply the softmax function to a vector of length \(K\) that has \(b_k + w_{(k)}^\top x\) at the \(k\)th coordinate.

\[\begin{equation} \label{eq:softeq} \hat{y}=\underbrace{S_{\text{softmax}} \big(\overbrace{b+W x}^{z\in \Re^K}\big)}_{a\in \Re^K}, \end{equation}\]

where \(\hat{y}\) is the predictionvector of \(\boldsymbol{\phi}(x)\) with

\[\begin{equation} \label{eq:mult-params-vec-mat} b = \left[ \begin{matrix} b_1\\ \vdots\\ b_K \end{matrix} \right], \qquad \text{and} \qquad {W}= \begin{bmatrix} ~\text{------} & w_{(1)}^\top & \text{------} \\[5pt] ~\text{------} & w_{(2)}^\top & \text{------} \\[5pt] & \vdots & \\[5pt] ~\text{------} & w_{(K)}^\top & \text{------}\\ \end{bmatrix}. \end{equation}\]

  • Softmax model/Multinomial Regression is a Shallow Neural Network

- Classifier: an output vector \(\hat{y}\) is a probability vector.

  • Choose the class that has the highest probability

\[\begin{equation} \label{eq:argmax-mp} \widehat{\cal Y}=\underset{k \in\{1, \ldots, K\}}{\operatorname{argmax}} ~\hat{y}_k. \end{equation}\]

  • A practice on MNIST data (only on 5000 images)
library(glmnet)
Ytrain[which(Ytrain==-1)] <- 0
fit=cv.glmnet(Xtrain[1:1000,],Ytrain[1:1000,],family = "multinomial",type.measure = "class")
plot(fit)

  • Evaluate classifier on test data
library(IMIFA)
pred=predict(fit,Xtest,s=fit$lambda.min,type="class")-1
par(mfrow=c(2,3))
for(i in 1:6){
  show_digit(Xtest[i,])
  title(sprintf("prediction = %s",pred[i]))
}

mean(labels_test_set==pred)
[1] 0.8313
  • Improve using more images
library(nnet)
model <- multinom(Ytrain[1:20000,] ~., family = "multinomial", MaxNWts =10000000, maxit=50,data=as.data.frame(Xtrain[1:20000,]));
# weights:  7860 (7065 variable)
initial  value 46051.701860 
iter  10 value 9835.249814
iter  20 value 7772.741852
iter  30 value 6666.130513
iter  40 value 5630.991143
iter  50 value 4902.647609
final  value 4902.647609 
stopped after 50 iterations
results <- predict(model, newdata=Xtest, type='probs')
prediction <- max.col(results)
prediction <- prediction - 1
cl <- mean(prediction != labels_test_set)
print(paste('Accuracy', 1 - cl))
[1] "Accuracy 0.894"

Beyond linear bundary decision

  • Back to the case \(k=2\) with a sigmoid model

  • Consider a scenario with \(p=2\) features

load("versatile-boundaries.RData")
library(ggplot2)
ggplot(data) + geom_point(aes(x = x,y = y,color = as.character(label)), size = 1) +
  theme_bw(base_size = 15) +
  xlim(-2.5, 1.5) +
  ylim(-2.5, 2.5) +
  coord_fixed(ratio = 0.8) +
  theme(axis.ticks=element_blank(),
        panel.grid.major = element_blank(),
        panel.grid.minor = element_blank(),
        axis.text=element_blank(),
        axis.title=element_blank(),
        legend.position = "none")

  • We first use a sigmoid model and check the decision boundary
train_data <- data
trainX <- train_data[, c(1, 2)]
trainY <- train_data[, 3]
trainY <- ifelse(trainY == 1, 0, 1)
data.glm <- data.frame(Y=trainY,X1=trainX[,1],X2=trainX[,2])
model.logistic <- glm(Y~X1+X2,data=data.glm,family=binomial)
## As a reminder we check the shape of our classifier
step <- 0.01
x_min <- min(trainX[, 1]) - 0.2
x_max <- max(trainX[, 1]) + 0.2
y_min <- min(trainX[, 2]) - 0.2
y_max <- max(trainX[, 2]) + 0.2
grid <- as.matrix(expand.grid(seq(x_min, x_max, by = step), seq(y_min,
                                                                y_max, by = step)))

data.grid <- data.frame(X1=grid[,1],X2=grid[,2])

Z <- predict(model.logistic,newdata=data.grid,type="response")
Z <- ifelse(Z <0.5, 1, 2)


g1 <- ggplot() +
  geom_tile(aes(x = grid[, 1], y = grid[, 2], fill = as.character(Z)), alpha = 0.3, show.legend = F)+
  geom_point(data = train_data, aes(x = x, y = y, color = as.character(trainY)),size = 1)+
  theme_bw(base_size = 15) + coord_fixed(ratio = 0.8) +
  labs(x=expression(x[1]),cex=2) +labs(y=expression(x[2]))+
  theme(axis.ticks = element_blank(), panel.grid.major = element_blank(),
       panel.grid.minor = element_blank(), legend.position = "none",axis.title=element_text(size=18,face="italic"))
  
g1

  • It is a bad linear classifier:

\[ P[Y=1|X_1=x_1,X_2=x_2]=\frac{1}{1+e^{-(b+w_1x_1+w_2x_2)}} \]

  • We can use polynomial feature engineering:

\[\begin{equation} \label{eq:quad-decision-boundry} \tilde{b} + \tilde{w}_1 x_1 + \tilde{w}_2 x_2 + \tilde{w}_3 x_1^2 + \tilde{w}_4 x_2^2 + \tilde{w}_5 x_1 x_2 \ge 0. \end{equation}\]

  • Feature engineering allows for non linear decision boundaries.
model.logistic.nl2 <- glm(Y~polym(X1, X2, degree=2, raw=TRUE),data=data.glm,family=binomial)
glm.fit: fitted probabilities numerically 0 or 1 occurred
Z <- predict(model.logistic.nl2,newdata=data.grid,type="response")
Z <- ifelse(Z <0.5, 1, 2)

g2 <- ggplot() +
  geom_tile(aes(x = grid[, 1], y = grid[, 2], fill = as.character(Z)), alpha = 0.3, show.legend = F)+
  geom_point(data = train_data, aes(x = x, y = y, color = as.character(trainY)),size = 1)+
  theme_bw(base_size = 15) + coord_fixed(ratio = 0.8) +
  theme(axis.ticks = element_blank(), panel.grid.major = element_blank(),
        panel.grid.minor = element_blank(), axis.text = element_blank(),
        axis.title = element_blank(), legend.position = "none")+
  theme(axis.title=element_text(size=18,face="italic"))

g2+ labs(x=expression(x[1]),cex=2) +labs(y=expression(x[2]),cex=2)

  • Investigate higher order
model.logistic.nl3 <- glm(Y~polym(X1, X2, degree=4, raw=TRUE),data=data.glm,family=binomial)
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred
model.logistic.nl4 <- glm(Y~polym(X1, X2, degree=8, raw=TRUE),data=data.glm,family=binomial)
glm.fit: fitted probabilities numerically 0 or 1 occurred
Z <- predict(model.logistic.nl3,newdata=data.grid,type="response")
Z <- ifelse(Z <0.5, 1, 2)
par(mfrow=c(1,2))
g2 <- ggplot() +
  geom_tile(aes(x = grid[, 1], y = grid[, 2], fill = as.character(Z)), alpha = 0.3, show.legend = F)+
  geom_point(data = train_data, aes(x = x, y = y, color = as.character(trainY)),size = 1)+
  theme_bw(base_size = 15) + coord_fixed(ratio = 0.8) +
  theme(axis.ticks = element_blank(), panel.grid.major = element_blank(),
        panel.grid.minor = element_blank(), axis.text = element_blank(),
        axis.title = element_blank(), legend.position = "none")+
  theme(axis.title=element_text(size=18,face="italic"))

g2+ labs(x=expression(x[1]),cex=2) +labs(y=expression(x[2]),cex=2)



Z <- predict(model.logistic.nl4,newdata=data.grid,type="response")
Z <- ifelse(Z <0.5, 1, 2)
g3 <- ggplot() +
  geom_tile(aes(x = grid[, 1], y = grid[, 2], fill = as.character(Z)), alpha = 0.3, show.legend = F)+
  geom_point(data = train_data, aes(x = x, y = y, color = as.character(trainY)),size = 1)+
  theme_bw(base_size = 15) + coord_fixed(ratio = 0.8) +
  labs(x=expression(x[1]),cex=2) +labs(y=expression(x[2]))+
  theme(axis.ticks = element_blank(), panel.grid.major = element_blank(),
        panel.grid.minor = element_blank(), legend.position = "none",axis.title=element_text(size=18,face="italic"))


g3+ labs(x=expression(x[1]),cex=2) +labs(y=expression(x[2]),cex=2)

  • higher orders might gain more expressivity but Higher order models yield obscure classification decision boundaries.

  • Certainly appear like an over-fit.

  • New set of features could become highly correlated and that can cause difficulty in inference of parameters.

Multi-class classification: synthetic data example

clr1 <- c(rgb(1,0,0,1),rgb(0,1,0,1),rgb(0,0,1,1),rgb(0.5,0.5,0.5,1))
clr2 <- c(rgb(1,0,0,.1),rgb(0,1,0,.1),rgb(0,0,1,.1),rgb(0.5,0.5,0.5,.5))
x <- c(.4,.55,.65,.9,.1,.35,.5,.15,.2,.85,0.2,0.7,0.3,0.5,0.6,0.55,0.4)
y <- c(.85,.95,.8,.87,.5,.55,.5,.2,.1,.3,0.7,0.5,0.3,0.7,0.6,0.65,0.7)
z <- c(1,2,2,2,1,0,0,1,0,0,1,2,1,3,3,3,3)
df <- data.frame(x,y,z)
plot(x,y,pch=19,cex=2,col=clr1[z+1],ylab=expression(x[2]),xlab=expression(x[1]),cex.lab=1.4)

#write.csv(df,file="synthetic_data_4_class.csv",row.names = FALSE)
library(nnet)
model.mult <- multinom(z~x+y,data=df)
# weights:  16 (9 variable)
initial  value 23.567004 
iter  10 value 8.943075
iter  20 value 7.332678
iter  30 value 7.299143
iter  40 value 7.245881
iter  50 value 7.232151
iter  60 value 7.180802
iter  70 value 7.165842
iter  80 value 7.135699
iter  90 value 7.116795
iter 100 value 7.096799
final  value 7.096799 
stopped after 100 iterations
pred_mult <- function(x,y){
  res <- predict(model.mult,
                 newdata=data.frame(x=x,y=y),type="probs")
  apply(res,MARGIN=1,which.max)
}
x_grid<-seq(0,1,length=601)
y_grid<-seq(0,1,length=601)
z_grid <- outer(x_grid,y_grid,FUN=pred_mult)


image(x_grid,y_grid,z_grid,col=clr2,ylab=expression(x[2]),xlab=expression(x[1]),cex.lab=1.4)

points(x,y,pch=19,cex=2,col=clr1[z+1])
legend("topleft", inset=0.02, legend=c("class 1", "class 2","class 3","class 4"),
       col=clr1[c(1,3,2,4)], cex=0.9, pch=c(19,19))


model.mult <- multinom(z~polym(x,y, degree=2, raw=TRUE),data=df)
# weights:  28 (18 variable)
initial  value 23.567004 
iter  10 value 8.124558
iter  20 value 6.923017
iter  30 value 6.507148
iter  40 value 5.878525
iter  50 value 5.455237
iter  60 value 5.288689
iter  70 value 4.723312
iter  80 value 4.631339
iter  90 value 4.520595
iter 100 value 4.348960
final  value 4.348960 
stopped after 100 iterations
x_grid<-seq(0,1,length=601)
y_grid<-seq(0,1,length=601)
z_grid <- outer(x_grid,y_grid,FUN=pred_mult)

image(x_grid,y_grid,z_grid,col=clr2,ylab=expression(x[2]),xlab=expression(x[1]),cex.lab=1.4)

points(x,y,pch=19,cex=2,col=clr1[z+1])
legend("topleft", inset=0.02, legend=c("class 1", "class 2","class 3","class 4"),
       col=clr1[c(1,3,2,4)], cex=0.9, pch=c(19,19))



model.mult <- multinom(z~polym(x,y, degree=8, raw=TRUE),data=df)
# weights:  184 (135 variable)
initial  value 23.567004 
iter  10 value 5.859693
iter  20 value 4.064641
iter  30 value 2.910536
iter  40 value 0.007991
final  value 0.000063 
converged
x_grid<-seq(0,1,length=601)
y_grid<-seq(0,1,length=601)
z_grid <- outer(x_grid,y_grid,FUN=pred_mult)


image(x_grid,y_grid,z_grid,col=clr2,ylab=expression(x[2]),xlab=expression(x[1]),cex.lab=1.4)

points(x,y,pch=19,cex=2,col=clr1[z+1])
legend("topleft", inset=0.02, legend=c("class 1", "class 2","class 3","class 4"),
       col=clr1[c(1,3,2,4)], cex=0.9, pch=c(19,19))

Optimization and loss function

  • Learning activity involves optimization

  • Learning is the process of seeking model parameters that are ``best’’ for some given task.

  • Loss function is generally used as proxy for minimization of the actual performance measures that are of interest

  • Example: classification problems aim to get the most accurate classifier. In such a case, optimization is typically not carried out directly on the accuracy measure but rather on a loss function such as the mean square error, or cross entropy

  • For binary outcome, we use binary cross entropy

\[\begin{equation} \label{eq:bin-cross-enty} \text{CE}_{\text{binary}}({y},\hat{y}) =- \Big( y \log{\big(\hat{y} \big)}+(1-y )\log{\big(1-\hat{y} \big)}\Big), \end{equation}\]

  • For `numerical outcome``, we generally use the Square error loss

\[ C_i(\theta)=({y} - \hat{y})^2. \]

  • For categorical outcome, we generally use the categorical cross entropy. For a label \(y \in \{1,\ldots,K\}\) and a probability vector \(\hat{y}\) of length \(K\): % \[\begin{equation} \label{eq:cat-cross-entr} \text{CE}_\text{categorical}(y, \hat{y}) = - \sum_{k=1}^K {{\mathbf 1}\{y = k\}} \log \hat{y}_k \end{equation}\]

  • Why is matter to choose the appropriate loss function ? loss landscape of Sigmoid model

- (a) Using the squared loss and (b) Using the binary cross entropy loss

  • Some Benefits of Cross Entropy Loss:

    • the cross entropy loss landscape is more manageable to navigate for an optimization algorithm like gradient descent.
    • In the case of logistic regression, cross entropy always yields a convex loss landscape
    • Here, the squared error loss yield non-convex loss landscape,, multiple local minima as well as saddle points.
  • Optimization of the loss function through Gradient Descent algorithms

  • This gradient descent procedure executes over iterations indexed by \(t=0,1,2,\ldots\)

  • Works by taking small steps in the direction opposite to the gradient.

  • That is, it traverses downhill each time trying to descend in the steepest direction.

  • Steps are determined by a fixed \(\alpha > 0\) called the learning rate.

  • After some initialization \(\theta^{(0)} = \theta_{init}\), in each iteration \(t\), the next vector \(\theta^{(t+1)}\) is obtained via,

\[\begin{equation} \label{eq:gdls1} \theta^{(t+1)} = \theta^{(t)} - \alpha \nabla C(\theta^{(t)}). \end{equation}\]

  • Example: linear model with an intercept and one feature

  • Convergence can depend of the learning rate choice !!!

  • Standardization of Inputs can help the optimization

  • Illustration of gradient descent on Wisconsin breast cancer dataset

  • We split he observations into \(n_{\text{train}} = 456\) and \(n_{\text{test}}=113\).

  • We use a model with \(p=10\) features (\(d=11\)) and learn the parameters via gradient descent with some arbitrary initilization.

LS0tCnRpdGxlOiAiQSBjcmFzaCBjb3Vyc2Ugb24gdXNpbmcgbWFjaGluZSBsZWFybmluZyBtZXRob2RzIGVmZmVjdGl2ZWx5IGluIHByYWN0aWNlIgphdXRob3I6IAogIG5hbWU6IEJlbm9pdCBMaXF1ZXQgYW5kIFNhcmF0IE1va2EKICBhZmZpbGlhdGlvbjogU2Nob29sIG9mIE1hdGhhbWV0aWNzIGFuZCBQaHlzaWNhbCBTY2llbmNlcwogIGhlYWRlci1pbmNsdWRlczogXHVzZXBhY2thZ2V7YW1zbWF0aH0Kb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgdGhlbWU6IGNlcnVsZWFuCiAgICBoaWdobGlnaHQ6IGthdGUKLS0tCgogCgpXZWxjb21lIHRvIHRoaXMgb25lLWRheSB3b3Jrc2hvcDogKipBIGNyYXNoIGNvdXJzZSBvbiB1c2luZyBtYWNoaW5lIGxlYXJuaW5nIG1ldGhvZHMgZWZmZWN0aXZlbHkgaW4gcHJhY3RpY2UqKgoKLSBTb21lIG1hdGVyaWFscyBhbmQgaWxsdXN0cmF0aW9uIGFyZSBiYXNlZCBvbiAqKkNoYXB0ZXIgMioqIGFuZCAzIG9mIFtUaGUgTWF0aGVtYXRpY2FsIEVuZ2luZWVyaW5nIG9mIERlZXAgTGVhcm5pbmddKGh0dHBzOi8vZGVlcGxlYXJuaW5nbWF0aC5vcmcvKQoKLSBEYXRhIGFyZSBhdmFpbGFibGUgYXQgaHR0cHM6Ly9naXRodWIuY29tL2Jlbm9pdC1saXF1ZXQvU1NBLU1BUFMtTUwKCiMgQ09VUlNFIE9VVExJTkUKCi0gOTowMCB0byAxMDo0NTogU3VwZXJ2aXNlZCBMZWFybmluZyAocGFydCAxKSAKLSAxMDo0NSB0byAxMToxNTogQnJlYWsgKG1pZ2h0IG5lZWQgYSBjb2ZmZWUpCi0gMTE6MTUgdG8gMTI6NDU6IFN1cGVydmlzZWQgTGVhcm5pbmcgKHBhcnQgMikKLSAxMjo0NSB0byAxMzo0NTogTHVuY2ggQnJlYWsgCi0gMTNoNDUgdG8gMTU6MTU6IFVuc3VwZXJ2aXNlZCBMZWFybmluZyAocGFydCAxKSAKLSAxNToxNSB0byAxNTo0NTogQnJlYWsgKG1pZ2h0IG5lZWQgYW5vdGhlciBjb2ZmZWUpCi0gMTU6NDUgdG8gMTc6MDA6IFVuc3VwZXJ2aXNlZCBMZWFybmluZyAocGFydCAyKQoKIyBNYWNoaW5lIExlYXJuaW5nIChJbnRyb2R1Y3Rpb24pCgojIyBEZWZpbml0aW9uCgpUb20gTWl0Y2hlbGwgKDE5OTgpOgpfYGBBIGNvbXB1dGVyIHByb2dyYW0gaXMgc2FpZCB0byBsZWFybiBmcm9tIGV4cGVyaWVuY2UgRSB3aXRoIHJlc3BlY3QgdG8gc29tZSBjbGFzcyBvZiB0YXNrcyBUIGFuZCBwZXJmb3JtYW5jZSBtZWFzdXJlIFAsIGlmIGl0cyBwZXJmb3JtYW5jZSBhdCB0YXNrcyBpbiBULCBhcyBtZWFzdXJlZCBieSBQLCBpbXByb3ZlcyB3aXRoIGV4cGVyaWVuY2UgRS4nJ18KClN0ZXBoZW4gQm95ZCAoMjAxNik6Cl9gYG1hY2hpbmUgbGVhcm5pbmc6IGV4dHJhY3QgaW5mb3JtYXRpb24gZGlyZWN0bHkgZnJvbSBoaXN0b3JpY2FsIGRhdGEgYW5kIGV4dHJhcG9sYXRlIHRvIGFjaGlldmUgYSB0YXNrICggZS5nLiBtYWtlIHByZWRpY3Rpb25zKScnXwoKCiFbXShmaWd1cmUyXzFfYV90cmFpbmluZ19wcmVkaWN0aW9uLnBuZykKCgojIyBBIGZpcnN0IEV4YW1wbGU6IAoKQ29uc2lkZXIgdGhlIGRhdGEgZnJvbSBfQnJlYXN0IENhbmNlciBXaXNjb25zaW4gKERpYWdub3N0aWMpXyAoV0JDRCkgW2RhdGFzZXRdKGh0dHBzOi8vYXJjaGl2ZS5pY3MudWNpLmVkdS9tbC9kYXRhc2V0cy9CcmVhc3QrQ2FuY2VyK1dpc2NvbnNpbislMjhEaWFnbm9zdGljJTI5KQoKCi0gR29hbCBpcyB0byBwcmVkaWN0IGlmIGEgYGBiZW5pZ25gYCAoWSA9IDApIG9yIGEgYGBtYWxpZ25hbnRgYCAoWSA9IDEpIGx1bXBzIG9mIGEgYnJlYXN0IG1hc3MuCgotIEhpc3RvcmljYWwgZGF0YSBjb25zaXN0cyBvZiBhIGxhcmdlIG51bWJlciBvZiBwYXRpZW50IHJlY29yZHMKCi0gMzAgKD0kZCQpIGNoYXJhY3RlcmlzdGljcyBvZiBpbmRpdmlkdWFsIGNlbGxzIG9mIGJyZWFzdCBjYW5jZXIKCi0gIVtdKGJyZWFzdC5wbmcpCgotIFVzZSBhIG1hY2hpbmUgbGVhcm5pbmcgYWxnb3JpdGhtIHRoYXQgb2JzZXJ2ZXMgdGhlc2UgZGF0YSwgcHJvZHVjZXMgYSBwcmVkaWN0b3IKCi0gUHJlZGljdG9yIHRha2VzIGFzIGlucHV0IDMwIHZhbHVlcywgcmV0dXJucyBhIHNpbmdsZSBCb29sZWFuIHByZWRpY3Rpb24gKGBgMGBgIG9yIGBgMWBgKQoKLSBUaGlzIGlzIGEgX2NsYXNzaWZpZXJfLCBzaW5jZSB3ZSBhcmUgcHJlZGljdGluZyBhbiBvdXRjb21lIHRoYXQgdGFrZXMgb25seSB0d28gdmFsdWVzCgotIEV2YWx1YXRlIG1vZGVsIGJ5IGl0cyBlcnJvciByYXRlIG9uIGEgKipzZXBhcmF0ZSB0ZXN0IHNldCBvZiBkYXRhKiosIG5vdCB1c2VkIHRvIGRldmVsb3AgdGhlIG1vZGVsCgotIEEgKipwcm9iYWJpbGlzdGljIG1vZGVsKiogcmV0dXJucyBhIF9wcm9iYWJpbGl0eV8gdGhhdCB0aGUgcGF0aWVudCBoYXMgYSBtYWxpZ25hbnQgbHVtcCwgbm90IGp1c3QgYSBCb29sZWFuCgojIyBBIHBvcHVsYXIgbW9kZWw6IHNpZ21vaWQgbW9kZWwKCiFbXShsb2dpc3RpY19hcmNoaXRlY3R1cmUucG5nKQoKKipTaWdtb2lkIG1vZGVsIGlzIGEgbG9naXN0aWMgbW9kZWwqKiAobW9yZSBkZXRhaWxzIGxhdHRlcikKCkl0IGdpdmVzIGEgcHJvYmFiaWxpdHkgYXMgb3V0cHV0OgoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6Zmlyc3Qtc2hhbGxvdy12aWV3fQpcaGF0e3l9PVx1bmRlcmJyYWNle1xzaWdtYVxsZWZ0KFxvdmVyYnJhY2V7Yit3Xlx0b3AgIHh9Xnt6fVxyaWdodCl9X3thfS4KXGVuZHtlcXVhdGlvbn0KCllvdSBjYW4gdHVybiBpbnRvIGEgKipjbGFzc2lmaWVyKioKCgoKXGJlZ2lue2VxdWF0aW9ufSAKXGxhYmVse2VxOmh5cGVyLXBsYW5lLWJhc2VkLWNsYXNzaWZpZXJ9Clx3aWRlaGF0e1xjYWwgWX0gPSAKXGJlZ2lue2Nhc2VzfQowfiAoXHRleHR0dHtCZW5pZ259KSwgJiBcdGV4dHtpZn0gXHF1YWQgIFxoYXR7eX0gXGxlIDAuNSwgXFwKMX4gKFx0ZXh0dHR7TWFsaWduYW59KSwgJiBcdGV4dHtpZn0gXHF1YWQgICBcaGF0e3l9ID4gMC41ClxlbmR7Y2FzZXN9ClxlbmR7ZXF1YXRpb259CgoKIyMgU2lnbW9pZC9Mb2dpc3RpYyBtb2RlbCBpbiBhY3Rpb24gCgotIFdlIHdpbGwgcnVuIHRoZSBzaWdtb2lkIG1vZGVsIHVzaW5nICoqZ2VuZXJhbGl6ZWQgbGluZWFyIG1vZGVsKiogZnJhbWV3b3JrCgotIEtlZXAgaW4gbWluZCAqKnNpZ21vaWQgbW9kZWwqKiBpcyBhICoqbG9naXN0aWMgbW9kZWwqKgoKLSBMZXRzIHJ1biBhIG1vZGVsIHdpdGggb25lIGZlYXR1cmUgYW5kIGEgbW9kZWwgd2l0aCAxMCBmZWF0dXJlcwoKYGBge3J9CmxvYWQoIkJyZWFzdF9jYW5jZXIuUkRhdGEiKQpsaWJyYXJ5KGRwbHlyKQpoZWFkKEJyZWFzdF9jYW5jZXJfZGF0YVssYygxOjYpXSkKZGF0YSA8LSBCcmVhc3RfY2FuY2VyX2RhdGEKZGltKGRhdGEpCmRhdGEgPC0gZGF0YSAlPiUgbXV0YXRlKGRpYWdub3Npc18wXzEgPSBpZmVsc2UoZGlhZ25vc2lzID09ICJNIiwgMSwgMCkpCnZhciA8LSBjKDEsMiw1LDYsOSwxMCwxMSwxMiwxNSwxNiwyNSwzMSkKZGF0YSA8LSBkYXRhWywtYygxLDIpXQpkYXRhIDwtIGRhdGFbLHZhcl0KY29sbmFtZXMoZGF0YSkKbGlicmFyeShST0NSKQpsaWJyYXJ5KGNhcmV0KQpzZXQuc2VlZCgxMDEpCnRyYWluaW5nIDwtIGNyZWF0ZURhdGFQYXJ0aXRpb24oZGF0YSRkaWFnbm9zaXNfMF8xLCBwPTAuOCwgbGlzdD1GQUxTRSkKdHJhaW4gPC0gZGF0YVsgdHJhaW5pbmcsIF0gIy0tPiB0cmFpbmluZyBkYXRhIAp0ZXN0IDwtIGRhdGFbIC10cmFpbmluZywgXSAjLS0+IHRlc3QgZGF0YQp0cmFpbmZ1bGwgPC0gdHJhaW5bLC1jKDEsMildCnVuaS5tb2RlbCA8LSBnbG0oZGlhZ25vc2lzXzBfMX5zbW9vdGhuZXNzX3dvcnN0LGZhbWlseT1iaW5vbWlhbCxkYXRhPXRyYWluZnVsbCkKZnVsbC5tb2RlbCA8LSBnbG0oZGlhZ25vc2lzXzBfMX4uLGZhbWlseT1iaW5vbWlhbCxkYXRhPXRyYWluZnVsbCkKc3VtbWFyeShmdWxsLm1vZGVsKSRjb2VmCmBgYAotIFdlIGNhbiBub3cgZm9ybmV3IHBhdGllbnRzIGdpdmUgYSBwcmVkaWN0aW9uIChwcm9iYWJpbGl0eSB2YWx1ZSkKCmBgYHtyfQpuZXcucGF0aWVudHMgPC0gdGVzdApuZXcucGF0aWVudHMKcC5mdWxsID0gcHJlZGljdChmdWxsLm1vZGVsLCBuZXcucGF0aWVudHMsIHR5cGU9InJlc3BvbnNlIikKcC5mdWxsWzE6MTBdCmBgYAoKLSBXZSBjYW4gYWxzbyB1c2UgdGhlIG1vZGVsIGFzIGEgY2xhc3NpZmllciAKCmBgYHtyLGV2YWw9RkFMU0V9Cm15LmNsYXNzaWZpZXIgPC0gZnVuY3Rpb24obW9kZWwscGF0aWVudCx0aHJlc2hvbGQ9MC41KSAgaWZlbHNlKHByZWRpY3QobW9kZWwsIHBhdGllbnQsIHR5cGU9InJlc3BvbnNlIik+dGhyZXNob2xkLDEsMCkKbXkuY2xhc3NpZmllcihmdWxsLm1vZGVsLG5ldy5wYXRpZW50c1sxOjEwLF0pCmBgYAoKLSBDb25mdXNpb24gbWF0cml4CgohW10oY29uZnVzaW9uX21hdHJpeC5wbmcpCgoKLSBQZXJmb3JtYW5jZSBtZWFzdXJlCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTphY2MtZGVmfQpcdGV4dHtBY2N1cmFjeX0gPSBcZnJhY3tcdGV4dHtUUH0gK1x0ZXh0e1ROfX17bl97XHRleHR7dGVzdH19fSwKXGVuZHtlcXVhdGlvbn0KCndoaWNoIGNhbiBiZSBtaXNsZWFkaW5nIGZvciB1bmJhbGFuY2VkIGRhdGEgKGVzcGVjaWFsbHkgcmFyZSBldmVudCkKCi0gTW9yZSByb2J1c3QgbWVhc3VyZXMgYXJlICoqc2Vuc2l0aXZpdHkqKiAoY2FsbGVkICoqcmVjYWxsKiopIGFuZCAqKnNwZWNpZmljaXR5KioKCgpgYGB7cn0KcHJlZC5mdWxsIDwtIG15LmNsYXNzaWZpZXIoZnVsbC5tb2RlbCx0ZXN0KQpyZXMuZnVsbCA8LSBjb25mdXNpb25NYXRyaXgoYXMuZmFjdG9yKHByZWQuZnVsbCksYXMuZmFjdG9yKHRlc3QkZGlhZ25vc2lzXzBfMSkscG9zaXRpdmU9IjEiKSAKdGFibGUocHJlZC5mdWxsLHRlc3QkZGlhZ25vc2lzXzBfMSkKcmVzLmZ1bGwkdGFibGUKcmVzLmZ1bGwkb3ZlcmFsbFsxXQpyZXMuZnVsbCRieUNsYXNzW2MoMSwyLDUsNildCmBgYAoKYGBge3J9CnByZWQudW5pIDwtIG15LmNsYXNzaWZpZXIodW5pLm1vZGVsLHRlc3QpCnJlcy51bmkgPC0gY29uZnVzaW9uTWF0cml4KGFzLmZhY3RvcihwcmVkLnVuaSksYXMuZmFjdG9yKHRlc3QkZGlhZ25vc2lzXzBfMSkscG9zaXRpdmU9IjEiKSAKcmVzLnVuaSR0YWJsZQpyZXMudW5pJG92ZXJhbGxbMV0KcmVzLnVuaSRieUNsYXNzW2MoMSwyLDUsNildCmBgYAoKCi0gQSBwb3B1bGFyIHdheSB0byBhdmVyYWdlICoqcHJlY2lzaW9uKiogYW5kICoqcmVjYWxsKiogaXMgYnkgY29uc2lkZXJpbmcgdGhlIGhhcm1vbmljIG1lYW4gb2YgdGhlIHR3byB2YWx1ZXMuIAoKLSBUaGlzIGlzIGNhbGxlZCB0aGUgKipGJF8xJCBzY29yZSoqIDoKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmYxLXNjb3JlfQpGXzEgPSBcZnJhY3syfXtcZnJhY3sxfXtcdGV4dHtQcmVjaXNpb259fSArIFxmcmFjezF9e1x0ZXh0e1JlY2FsbH19fSA9IDIgXGZyYWN7XHRleHR7UHJlY2lzaW9ufSBcdGltZXMgXHRleHR7UmVjYWxsfX17XHRleHR7UHJlY2lzaW9ufSArIFx0ZXh0e1JlY2FsbH19LgpcZW5ke2VxdWF0aW9ufQoKYGBge3J9CnJlcy51bmkkYnlDbGFzc1s3XQpyZXMuZnVsbCRieUNsYXNzWzddCmBgYAoKCi0gQmUgYXdhcmUgdGhhdCBjbGFzc2lmaWVyIGJhc2VkIG9uIHRocmVzaG9sZCBhbHRlcnMgY29uZnVzaW9uIG1hdHJpeAoKLSBSZWNlaXZlciBPcGVyYXRpbmcgQ2hhcmFjdGVyaXN0aWMgKFJPQykgY3VydmU6CgoKIVtdKFJPQ19jdXJ2ZS5wbmcpCgoKYGBge3IsZXZhbD1UUlVFfQoKcHJfZnVsbCA9IHByZWRpY3Rpb24ocHJlZC5mdWxsLCB0ZXN0JGRpYWdub3Npc18wXzEpCnBlcmZfZnVsbCA9IHBlcmZvcm1hbmNlKHByX2Z1bGwsIG1lYXN1cmUgPSAidHByIiwgeC5tZWFzdXJlID0gImZwciIpCgpwcl91bmkgPSBwcmVkaWN0aW9uKHByZWQudW5pLCB0ZXN0JGRpYWdub3Npc18wXzEpCnBlcmZfdW5pID0gcGVyZm9ybWFuY2UocHJfdW5pLCBtZWFzdXJlID0gInRwciIsIHgubWVhc3VyZSA9ICJmcHIiKQoKCmF1YzEgPSBwZXJmb3JtYW5jZShwcl9mdWxsLCBtZWFzdXJlID0gImF1YyIpCmF1YzEgPSBhdWMxQHkudmFsdWVzW1sxXV0KYXVjMiA9IHBlcmZvcm1hbmNlKHByX3VuaSwgbWVhc3VyZSA9ICJhdWMiKQphdWMyID0gYXVjMkB5LnZhbHVlc1tbMV1dCnByaW50KHBhc3RlKCJBVUMgZnVsbCB0ZXN0Iiwgc2lnbmlmKGF1YzEsZGlnaXRzPTQpKSkKcHJpbnQocGFzdGUoIkFVQyB1bmkgdGVzdCIsIHNpZ25pZihhdWMyLGRpZ2l0cz00KSkpCgoKbGlicmFyeShST0NpdCkKcjE9cm9jaXQocHJlZGljdCh1bmkubW9kZWwsIHRlc3QpLCB0ZXN0JGRpYWdub3Npc18wXzEsIG1ldGhvZCA9ICJiaW4iKQpyMz1yb2NpdChwcmVkaWN0KGZ1bGwubW9kZWwsIHRlc3QpLCB0ZXN0JGRpYWdub3Npc18wXzEsIG1ldGhvZCA9ICJiaW4iKQoKCgpwbG90KHIxJFRQUn5yMSRGUFIsIHR5cGUgPSAibCIsIHhsYWIgPSAiRmFsc2UgUG9zaXRpdmUgUmF0ZSIsIGx3ZCA9IDIsCiAgICAgeWxhYiA9ICJTZW5zaXRpdml0eSIsIGNvbD0gImdvbGQ0IixjZXgubGFiPTIsY2V4LmF4aXMgPSAyKQpncmlkKCkKbGluZXMocjMkVFBSfnIzJEZQUiwgbHdkID0gMiwgY29sID0gIm9yYW5nZSIpCnNlZ21lbnRzKDAsMCwxLDEsIGNvbCA9ICIyIiwgbHdkID0gMikKc2VnbWVudHMoMCwwLDAsMSwgY29sID0gImRhcmtncmVlbiIsIGx3ZCA9IDIpCnNlZ21lbnRzKDEsMSwwLDEsIGNvbCA9ICJkYXJrZ3JlZW4iLCBsd2QgPSAyKQoKbGVnZW5kKCJib3R0b21yaWdodCIsIGMoIlBlcmZlY3RseSBTZXBhcmFibGUiLCAKICAgICAgICAgICAgICAgICAgICAgICAgIlVuaXZhcmlhdGUiLCAiRnVsbCBtb2RlbCIsICJDaGFuY2UgTGluZSIpLCBjZXg9MiwKICAgICAgIGx3ZCA9IDIsIGNvbCA9IGMoImRhcmtncmVlbiIsICJnb2xkNCIsCiAgICAgICAgICAgICAgICAgICAgICAgICJvcmFuZ2UiLCAicmVkIiksIGJ0eSA9ICJuIikKCmBgYAoKCgojIyBNYWNoaW5lIGxlYXJuaW5nIG1vZGVsIHRheG9ub215CgotIGBzdXBlcnZpc2VkYCB2ZXJzdXMgYHVuc3VwZXJ2aXNlZGAgbW9kZWxzCgotIGBzdXBlcnZpc2VkIGxlYXJuaW5nYCBtb2RlbHMgcHJlZGljdCBzb21ldGhpbmcsIGdpdmVuIHNvbWUgb3RoZXIgdGhpbmdzCiAgICAtIGNhbGxlZCBhIHByZWRpY3Rpb24gbW9kZWwKICAgIC0gY2FsbGVkICoqcmVncmVzc2lvbioqIHdoZW4gd2UgcHJlZGljdCBhIHJlYWwgc2NhbGFyIG9yIHZlY3RvciB2YWx1ZQogICAgLSBjYWxsZWQgKipjbGFzc2lmaWNhdGlvbioqIHdoZW4gd2UgcHJlZGljdCBhIHZhbHVlIGZyb20gYSBmaW5pdGUgc2V0IHN1Y2ggYXMgYGBUcnVlYGA7IGBgRmFsc2VgYAogICAgCi0gYHVuc3VwZXJ2aXNlZCBsZWFybmluZ2AgbW9kZWxzIGp1c3QgY3JlYXRlIGEgbW9kZWwgb2YgdGhlIGRhdGEKICAgIC0gc29tZXRpbWVzIGNhbGxlZCBhIGRhdGEgbW9kZWwKICAgIC0gRGltZW5zaW9uIHJlZHVjdGlvbgogICAgLSBGaW5kIHBhdHRlcm4gaW4gdGhlIGRhdGEKCiMgRGF0YTogU2VlbiwgVW5zZWVuLCBUcmFpbmluZywgVGVzdGluZwogICAgCi0gRGlzdGluZ3Vpc2ggYmV0d2VlbiAqKnNlZW4gZGF0YSoqIGFuZCAqKnVuc2VlbiBkYXRhKiouCgotICoqU2VlbioqIGRhdGEgaXMgYXZhaWxhYmxlIGZvciBsZWFybmluZywgbmFtZWx5IGZvciB0cmFpbmluZyBvZiBtb2RlbHMsIG1vZGVsIHNlbGVjdGlvbiwgcGFyYW1ldGVyIHR1bmluZywgYW5kIHRlc3Rpbmcgb2YgbW9kZWxzLiAKCgotICoqVW5zZWVuKiogZGF0YSBpcyBlc3NlbnRpYWxseSB1bmxpbWl0ZWQuIEFsbCBkYXRhIGZyb20gdGhlIHJlYWwgd29ybGQgdGhhdCBpcyBub3QgYXZhaWxhYmxlIHdoaWxlIGxlYXJuaW5nIHRha2VzIHBsYWNlIGJ1dCBpcyBsYXRlciBhdmFpbGFibGUgd2hlbiB0aGUgbW9kZWwgaXMgdXNlZC4gVGhpcyBjYW4gYmUgZGF0YSBmcm9tIHRoZSBmdXR1cmUsIG9yIGRhdGEgdGhhdCB3YXMgbm90IGNvbGxlY3RlZCBvciBsYWJlbGxlZCB3aXRoIHRoZSBzZWVuIGRhdGEuIAoKCiFbXShEYXRhLnBuZykKCgotICoqTWFjaGluZSBsZWFybmluZyoqIHdvcmtzIHdlbGwgaWYgIG5hdHVyZSBvZiB0aGUgKipzZWVuIGRhdGEqKiBpcyBzaW1pbGFyIHRvICoqdW5zZWVuIGRhdGEqKi4gCgotIENvbW1vbiBwcmFjdGljZSBpcyB0byBzcGxpdCB0aGUgc2VlbiBkYXRhIGludG8gKip0cmFpbmluZyBkYXRhKiogYW5kICoqdGVzdGluZyBkYXRhKiogKGFsc28gbmFtZWQgKipob2xkIG91dCBzZXQqKikuIAoKLSAqKlRyYWluaW5nIGRhdGEqKiBpcyB1c2VkICBmb3IgbGVhcm5pbmcuCgotICoqVGVzdGluZyBkYXRhKiogZm9yIG1pbWlja2luZyBhIHNjZW5hcmlvIG9mIHVuc2VlbiBkYXRhLiAKCi0gVG8gZG8gKipyZWNhbGlicmF0ZSoqLCAqKmFkanVzdCoqLCBvciAqKnR1bmUgbW9kZWxzKiogb24gdGhlIHRyYWluaW5nIHNldCB3aGlsZSB0ZXN0aW5nIHJlcGVhdGVkbHkgb24gdGhlIHRlc3Qgc2V0LiAKCi0gUGVyZm9ybXMgYW4gKiphZGRpdGlvbmFsIHNwbGl0Kiogb2YgdGhlIHRyYWluaW5nIGRhdGEgYnkgKipyZW1vdmluZyoqIGEgY2h1bmsgb3V0IG9mIHRoZSB0cmFpbmluZyBkYXRhIGFuZCBjYWxsaW5nIGl0IHRoZSAqKnZhbGlkYXRpb24gc2V0KiouCgotIFN0YXRpc3RpY2FsIGFwcHJvYWNoZXMgYGBnZW5lcmFsbHlgYCB1c2UgYWxsIGF2YWlsYWJsZSBkYXRhIGFuZCBldmFsdWF0ZSBxdWFsaXR5IG9mIG1vZGVscyB1c2luZyBzZWxlY3Rpb24gY3JpdGVyaW9uIGFzICAqKkFrYWlrZSBpbmZvcm1hdGlvbiBjcml0ZXJpb24gKEFJQykqKiBvciAqKipCYXllc2lhbiBpbmZvcm1hdGlvbiBjcml0ZXJpb24gKEJJQykqKi4gCgoKLSBTb21ldGltZXMgaW5zdGVhZCBvZiB1c2luZyBhICoqdmFsaWRhdGlvbiBzZXQqKiB3ZSBjYW4gZG8gKiprLWZvbGQgY3Jvc3MgdmFsaWRhdGlvbioqIAoKCiAgICAKIyMgRGF0YSBQcmVwcm9jZXNzaW5nCgoKLSAqKnN0YW5kYXJkaXphdGlvbiBvZiB0aGUgZGF0YSoqOiAgIHN1YnRyYWN0aW9uIG9mIHRoZSBtZWFuIG9mIGVhY2ggZmVhdHVyZSBhbmQgZGl2aXNpb24gYnkgdGhlIHN0YW5kYXJkIGRldmlhdGlvbiBvZiB0aGUgZmVhdHVyZS4gCgotICoqc2FtcGxlIG1lYW4qKiBhbmQgKipzYW1wbGUgc3RhbmRhcmQgZGV2aWF0aW9uKioKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOnN0YXRzLW1lYW4tdmFyfQpcb3ZlcmxpbmV7eH1faSA9IFxmcmFjezF9e259IFxzdW1fe2o9MX1ebiB4X2leeyhqKX0sClxxcXVhZApzXjJfaSA9IFxmcmFjezF9e259IFxzdW1fe2o9MX1ebiAoeF9pXnsoail9IC0gXG92ZXJsaW5le3h9X2kpXjIuClxlbmR7ZXF1YXRpb259CgotICoqc3RhbmRhcmRpemF0aW9uKiogCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTpyZWYtc3RhbmQten0Kel57KGopfV9pID0gXGZyYWN7eF57KGopfV9pIC0gXG92ZXJsaW5le3h9X2l9e3NfaX0KXHFxdWFkClx0ZXh0e2Zvcn0KXHFxdWFkCmo9MSxcbGRvdHMsbi4KXGVuZHtlcXVhdGlvbn0KCi0gRm9yIGZlYXR1cmUgJGkkLCAkel9pXnsoMSl9LCBcbGRvdHMsel9pXnsobil9JCwgaGFzIGEgc2FtcGxlIG1lYW4gb2YgZXhhY3RseSAkMCQgYW5kIGEgc2FtcGxlIHN0YW5kYXJkIGRldmlhdGlvbiBvZiBleGFjdGx5ICQxJC4gCgotIFN1Y2ggc3RhbmRhcmRpemF0aW9uIGlzIHVzZWZ1bCBhcyBpdCBwbGFjZXMgdGhlIGR5bmFtaWMgcmFuZ2Ugb2YgdGhlIG1vZGVsIGlucHV0cyBvbiBhICoqdW5pZm9ybSBzY2FsZSoqIGFuZCB0aHVzIGltcHJvdmVzIHRoZSAqKm51bWVyaWNhbCBzdGFiaWxpdHkqKiBvZiBhbGdvcml0aG1zLgoKLSBXZSB3aWxsIGRpc2N1c3MgaG93IHN1Y2ggKipzdGFuZGFyZGl6YXRpb24qKiBjYW4gYWxzbyBoZWxwICoqb3B0aW1pemF0aW9uIHBlcmZvcm1hbmNlKiouCgoKCiMjIExlYXJuaW5nICRcc2ltZXEkIE9wdGltaXphdGlvbgoKLSBMZWFybmluZyBhY3Rpdml0eSBpbnZvbHZlcyBfb3B0aW1pemF0aW9uXyBlaXRoZXIgZXhwbGljaXRseSBvciBpbXBsaWNpdGx5LgoKLSBUaGlzIGlzIGJlY2F1c2UgbGVhcm5pbmcgaXMgdGhlIHByb2Nlc3Mgb2Ygc2Vla2luZyBtb2RlbCBwYXJhbWV0ZXJzIHRoYXQgYXJlIGBgYmVzdGBgIGZvciBzb21lIGdpdmVuIHRhc2suIAoKLSBPcHRpbWl6ZSBzb21lICoqcGVyZm9ybWFuY2UgbWVhc3VyZSoqIHRoYXQgcXVhbnRpZmllcyBob3cgZ29vZCB0aGUgbW9kZWwgYXQgaGFuZCBwZXJmb3Jtcy4KCi0gRXhhbXBsZSwgdXNlICoqbWVhbiBzcXVhcmUgZXJyb3IqKiBjcml0ZXJpb24gZm9yIHJlZ3Jlc3Npb24gcHJvYmxlbXMKCi0gSW4gb3RoZXIgY2FzZXMsIGEgKipsb3NzIGZ1bmN0aW9uKiogaXMgdXNlZCBzdWNoIHRoYXQgbWluaW1pemF0aW9uIG9mIHRoZSBsb3NzIGZ1bmN0aW9uIGlzIGEgKipwcm94eSoqIGZvciBtaW5pbWl6YXRpb24gb2YgdGhlIGFjdHVhbCBwZXJmb3JtYW5jZSBtZWFzdXJlcyB0aGF0IGFyZSBvZiBpbnRlcmVzdC4gCgotIEV4YW1wbGUsIGZvciBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtcyB3ZSBhaW0gdG8gZ2V0IHRoZSBtb3N0IGFjY3VyYXRlIGNsYXNzaWZpZXIgYnV0IG9wdGltaXphdGlvbiBpcyB0eXBpY2FsbHkgbm90IGNhcnJpZWQgb3V0IGRpcmVjdGx5IG9uIHRoZSBhY2N1cmFjeSBtZWFzdXJlIGJ1dCByYXRoZXIgb24gYSAqKmxvc3MgZnVuY3Rpb24qKiBzdWNoIGFzIHRoZSAqKm1lYW4gc3F1YXJlIGVycm9yKiosIG9yICoqY3Jvc3MgZW50cm9weSoqIAoKCgojIFN1cGVydmlzZWQgbGVhcm5pbmcKCi0gTW9yZSBjb21tb24gZm9ybSBvZiBtYWNoaW5lIGxlYXJuaW5nIAoKLSBEYXRhIGlzIGNvbXByaXNlZCBvZiB0aGUgZmVhdHVyZXMgKGluZGVwZW5kZW50IHZhcmlhYmxlcykgJFgkIGFuZCB0aGUgbGFiZWxzIChkZXBlbmRlbnQgdmFyaWFibGVzLCByZXNwb25zZSB2YXJpYWJsZXMpICRZJC4KCi0gKipSZWdyZXNzaW9uIHByb2JsZW0qKiB3aGVuIHRoZSB2YXJpYWJsZSB0byBiZSBwcmVkaWN0ZWQgJFkkIGlzIGEgY29udGludW91cyBvciBudW1lcmljYWwgdmFyaWFibGUKCi0gKipDbGFzc2lmaWNhdGlvbiBwcm9ibGVtKiosIGluIGNhc2VzIHdoZXJlICRZJCBjb21lcyBmcm9tIHNvbWUgZmluaXRlIHNldCBvZiBsYWJlbCB2YWx1ZXMuCgoKCgoKIyMgQmFzaWNzOiBsaW5lYXIgbW9kZWxzCgoKLSBTdGFydCBzaW1wbGUgd2l0aCBhbiBleGFtcGxlOiAqKkhvdXNpbmcgZGF0YSoqCgotICoqdW5pdmFyaWF0ZSoqIGV4YW1wbGU6ICR4JCBpcyB0aGUgYXZlcmFnZSBudW1iZXIgb2Ygcm9vbXMgcGVyIGR3ZWxsaW5nIGFuZCAkeSQgaXMgdGhlIG1lZGlhbiB2YWx1ZSBvZiBvd25lci1vY2N1cGllZCBob21lcyBpbiB0aG91c2FuZHMgb2YgZG9sbGFycy4gCgotIEEgcmVncmVzc2lvbiBtb2RlbCAkeSA9IGZfXHRoZXRhKHgpJCBhdHRlbXB0cyB0byBwcmVkaWN0IHRoZSBtZWRpYW4gaG91c2UgcHJpY2UgYXMgYSBmdW5jdGlvbiBvZiB0aGUgYXZlcmFnZSBudW1iZXIgb2Ygcm9vbXMuIAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6c2ltcGxlLWxpbmVhci1yZWd9CnkgPSBcYmV0YV8wICsgXGJldGFfMSB4ICsgXGVwc2lsb24sClxlbmR7ZXF1YXRpb259CgoKCmBgYHtyfQpsaWJyYXJ5KE1BU1MpCmxpYnJhcnkodGlkeXZlcnNlKQpkYXRhKCJCb3N0b24iLCBwYWNrYWdlID0gIk1BU1MiKQppbmQgPC0gd2hpY2goQm9zdG9uJG1lZHY9PTUwKQpCb3N0b24ucyA8LSBCb3N0b25bLWluZCxdCnRyYWluLmRhdGEgIDwtIEJvc3Rvbi5zCgptb2RlbDEgPC0gbG0obWVkdn5ybSxkYXRhPXRyYWluLmRhdGEpCgoKcDEgPC0gZ2dwbG90KHRyYWluLmRhdGEsIGFlcyhybSwgbWVkdikpICsKICBnZW9tX3BvaW50KHNpemU9MikgKyBzdGF0X3Ntb290aChtZXRob2QgPSAibG0iLCBjb2wgPSAicmVkIikgKwogIHhsYWIoJ0F2ZXJhZ2UgbnVtYmVyIG9mIHJvb21zIHBlciBkd2VsbGluZyAocm0pJykgKyB5bGFiKCdIb3VzZSBwcmljZXMgaW4gJDEwMDAgKG1lZHYpJykrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gJ2JvdHRvbScpICArIHRoZW1lX2J3KCkKcDEgKyB0aGVtZShheGlzLnRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEwKSkrIHRoZW1lKGF4aXMudGl0bGUgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEwKSkgICAKYGBgCgoKLSBOb3QgZXZlcnl0aGluZyBpcyBsaW5lYXI6IFBvbHlub21pYWwgbW9kZWwKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOnBvbHktMi1yZWd9CnkgPSBcYmV0YV8wICsgXGJldGFfMSB4ICsgXGJldGFfMiB4XjIgKyBcZXBzaWxvbi4KXGVuZHtlcXVhdGlvbn0KCgpgYGB7cn0KbW9kZWwubG0gPC0gbG0obWVkdn5sc3RhdCxkYXRhPXRyYWluLmRhdGEpCm1vZGVsLnF1YWQgPC0gbG0obWVkdn5sc3RhdCtJKGxzdGF0XjIpLGRhdGE9dHJhaW4uZGF0YSkKCnAyIDwtIGdncGxvdCh0cmFpbi5kYXRhLCBhZXMobHN0YXQsIG1lZHYpICkgKwogIGdlb21fcG9pbnQoc2l6ZT0yKSArCiAgc3RhdF9zbW9vdGgobWV0aG9kID0gbG0sIGZvcm11bGEgPSB5IH4gcG9seSh4LCAyLCByYXcgPSBUUlVFKSkrCiAgc3RhdF9zbW9vdGgobWV0aG9kID0gbG0sIGZvcm11bGEgPSB5IH4geCxjb2w9J3JlZCcpKwogIHhsYWIoJ0xvd2VyIHN0YXR1cyBvZiB0aGUgcG9wdWxhdGlvbiBpbiAlIChsc3RhdCknKSArIHlsYWIoJ0hvdXNlIHByaWNlcyBpbiAkMTAwMCAobWVkdiknKSsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAnYm90dG9tJykgICsgdGhlbWVfYncoKQpwMiArIHRoZW1lKGF4aXMudGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTApKSsgdGhlbWUoYXhpcy50aXRsZSA9IGVsZW1lbnRfdGV4dChzaXplID0gMTApKSAgIApgYGAKIyMgTGVhcm5pbmcgdGhlIGxpbmVhciBtb2RlbAoKLSBDb25zaWRlciBhIHRyYWluaW5nIGRhdGFzZXQgJFxtYXRoY2Fse0R9PVx7KHheeygxKX0seV57KDEpfSksXGxkb3RzLCh4Xnsobil9LHleeyhufSlcfSQgY29tcG9zZWQgb2YgYSBjb2xsZWN0aW9uIG9mICRuJCBzYW1wbGVzLiAKCi0gKipEZXNpZ24gbWF0cml4KiogJFgkIGZvciB0aGUgZmVhdHVyZXMsIGFuZCB0aGUgY29ycmVzcG9uZGluZyBvdXRwdXQgcmVzcG9uc2UgdmVjdG9yICR5JCwgdmlhLAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6ZGVzaWdufQpYPVxiZWdpbntibWF0cml4fQogXHZlcnQgJiBcdmVydCAgICYgJlx2ZXJ0IFxcIAogMSAmeF97KDEpfSAgJlxkb3RzICZ4X3socCl9IFxcIAogXHZlcnQgJiBcdmVydCAmICAmIFx2ZXJ0IApcZW5ke2JtYXRyaXh9ClxxdWFkIFx0ZXh0cm17d2l0aH0gClxxdWFkIHhfeyhpKX09XGJlZ2lue2JtYXRyaXh9CnhfaV57KDEpfSBcXApcdmRvdHMgXFwKeF9pXnsobil9ClxlbmR7Ym1hdHJpeH0sClxxdWFkClx0ZXh0cm17YW5kfQpccXVhZAp5PQpcYmVnaW57Ym1hdHJpeH0KeV57KDEpfSBcXAoleV57KDIpfSBcXApcdmRvdHMgXFwKeV57KG4pfQpcZW5ke2JtYXRyaXh9Ci4KXGVuZHtlcXVhdGlvbn0KCgotIExpbmVhciBtb2RlbCBmb3IgYWxsIHRoZSBzYW1wbGVzIG9mIHRoZSB0cmFpbmluZyBzZXQgdmlhClxbCnk9WFx0aGV0YSsgXGVwc2lsb24sICAKXF0Kd2l0aCAkXGVwc2lsb249KFxlcHNpbG9uXzEsXGRvdHMsXGVwc2lsb25fbikkIAoKLSBEZWZpbmUgdGhlIHByZWRpY3RlZCBvdXRwdXQgdmVjdG9yIG9mIHRoZSBtb2RlbCBmb3IgdGhlIGlucHV0IHRyYWluaW5nIGRhdGEgdmlhLApcWwpcaGF0e3l9PVhcd2lkZWhhdHtcdGhldGF9LApccXF1YWQKXHRleHR7d2hlcmV9ClxxcXVhZApcaGF0e3l9ID0gClxiZWdpbntibWF0cml4fQpcaGF0e3l9XnsoMSl9IFxcCiV5XnsoMil9IFxcClx2ZG90cyBcXApcaGF0e3l9Xnsobil9ClxlbmR7Ym1hdHJpeH0uCiUoXGhhdHt5fV57KDEpfSxcbGRvdHMsXGhhdHt5fV57KG4pfSkuIApcXQotIEEgc3VpdGFibGUgbGVhcm5lZCB2YWx1ZSBmb3IgJFx3aWRlaGF0e1x0aGV0YX0kIHdpbGwgeWllbGQgJFxoYXR7eX1cYXBwcm94IHkkLiAKCi0gVGhpcyBjbG9zZW5lc3MgaXMgY2FwdHVyZWQgdmlhIGEgKipsb3NzIGZ1bmN0aW9uKio6ClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmdlbmVyYWwtYWRkaXRpdmUtbG9zc30KQyhcdGhldGEgXCw7IFwsIFxtYXRoY2FsIEQpPVxmcmFjezF9e259XHN1bV97aT0xfV5uQ19pKFx0aGV0YSkKXGVuZHtlcXVhdGlvbn0Kd2hlcmUgJENfaShcdGhldGEpOj1DX2koXHRoZXRhIFwsIDsgXCwgeV57KGkpfSwgXGhhdHt5fV57KGkpfSkkIGlzIHRoZSBsb3NzIGZvciB0aGUgJGkkLXRoIGRhdGEgc2FtcGxlLiBTcGVjaWZpY2FsbHkgJFx3aWRlaGF0e1x0aGV0YX0kIGlzIHR5cGljYWxseSBjaG9zZW4gc28gdGhhdCB0aGUgbG9zcyBmdW5jdGlvbiBpcyBtaW5pbWFsIGF0IHRoZSBwb2ludCAkXHRoZXRhID0gXHdpZGVoYXR7XHRoZXRhfSQuCgotIEZvciB0aGUgbGluZWFyIG1vZGVsOiAqKnNxdWFyZSBsb3NzKiogZnVuY3Rpb24gYWxzbyBjYWxsZWQgKipxdWFkcmF0aWMgbG9zcyoqIHdoZXJlIHRoZSBsb3NzIGZvciBlYWNoIGRhdGEgc2FtcGxlIGlzClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOnF1YWRyYXRpYy1sb3NzLW9uZS1vYnN9CkNfaShcdGhldGEpPSh7eX1eeyhpKX0gLSBcaGF0e3l9XnsoaSl9KV4yLgpcZW5ke2VxdWF0aW9ufQoKLSBMb3NzIGZvciB0aGUgZW50aXJlIHRyYWluaW5nIGRhdGEgY2FuIGJlIHJlcHJlc2VudGVkIGluIHRlcm1zIG9mIHRoZSAkTF8yJCBub3JtICRcfFxjZG90IFx8JCBvZiB0aGUgY29ycmVzcG9uZGluZyBlcnJvciB2ZWN0b3IsClxbCkMoXHRoZXRhO1xtYXRoY2FsIEQpID0gXGZyYWN7MX17bn1cc3VtX3tpPTF9Xm4oe3l9XnsoaSl9IC0gXGhhdHt5fV57KGkpfSleMiA9IFxmcmFjezF9e259XHx7eX0tXGhhdHt5fVx8XjIgClxdCgotIE9wdGltaXplOiAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmxlYXN0LXNxdWFyZXMtb3B0fQpcaGF0e1x0aGV0YX0KPVx0ZXh0cm17YXJnbWlufV97XHRoZXRhXGluIFxSZV5kfSBcZnJhY3sxfXtufXtcfCB5IC0gWFx0aGV0YVx8XjJ9ID0gXHRleHRybXthcmdtaW59X3tcdGhldGFcaW4gXFJlXmR9e1x8eSAtIFhcdGhldGFcfH1eMi4KXGVuZHtlcXVhdGlvbn0KCi0gIFRoZSBsZWFzdCBzcXVhcmVzIHNvbHV0aW9uIGNhbiBiZSBlYXNpbHkgZGVyaXZlZCBieSBmaXJzdCBjb21wdXRpbmcgdGhlIGdyYWRpZW50IG9mICR8fFhcdGhldGEteXx8XjIkIHdpdGggcmVzcGVjdCB0byAkXHRoZXRhJApcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTpncmFkTFN9ClxiZWdpbnthbGlnbmVkfQpcZnJhY3tccGFydGlhbCAgXHwgeSAtIFhcdGhldGFcfF4yfXtccGFydGlhbCBcdGhldGF9Jj0tMlheXHRvcCB5KzJYXlx0b3AgWFx0aGV0YS4KXGVuZHthbGlnbmVkfQpcZW5ke2VxdWF0aW9ufQoKLSBTZXR0aW5nIHRoZSBncmFkaWVudCB0byAwIHdlIGdldCAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOm5vcm1hbH0KWF5cdG9wIFhcdGhldGE9WF5cdG9wIHksClxlbmR7ZXF1YXRpb259CgotIFVuaXF1ZSBzb2x1dGlvbiB3aGVuIHRoZSAkZFx0aW1lcyBkJCBtYXRyaXggJFheXHRvcCBYJCwgYWxzbyBrbm93biBhcyB0aGUgKipHcmFtIG1hdHJpeCoqIG9mICRYJCwgaXMgaW52ZXJ0aWJsZS4KCi0gSW4gdGhpcyBjYXNlOiAgJFxoYXR7XHRoZXRhfT0oWF5cdG9wIFgpXnstMX1YXlx0b3AgeSQsIG9yLCBieSBzZXR0aW5nICRYXntcZGFnZ2VyfSA9ICAoWF5cdG9wIFgpXnstMX1YXlx0b3AkLCB3ZSBoYXZlLAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6Y2xvc2VkZm9ybX0KXGhhdHtcdGhldGF9PVhee1xkYWdnZXJ9IHksClxlbmR7ZXF1YXRpb259Cgp3aGVyZSAkWF57XGRhZ2dlcn0kIGlzICoqTW9vcmUtUGVucm9zZSBwc2V1ZG8taW52ZXJzZSoqIG9mICRYJC4gCgotIFVzaW5nIHRoZSBTVkQgKG1vcmUgZGV0YWlscyBsYXR0ZXIpIHdlIGNhbiByZXByZXNlbnQgdGhlICBNb29yZS1QZW5yb3NlIHBzZXVkby1pbnZlcnNlIGFzCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTpzdmQtYmFzZWQtbXBwaX0KIFhee1xkYWdnZXJ9ID0gViBcRGVsdGFeK1VeXHRvcCwKIFxlbmR7ZXF1YXRpb259CndoZXJlICRcRGVsdGFeKyQgY29udGFpbnMgdGhlIHJlY2lwcm9jYWxzIG9mIHRoZSBub24temVybyAoZGlhZ29uYWwpIGVsZW1lbnRzIG9mICRcRGVsdGEkLCBhbmQgaGFzICQwJCB2YWx1ZXMgZWxzZXdoZXJlLiAKCi0gVGhpcyBTVkQtYmFzZWQgcmVwcmVzZW50YXRpb24gaG9sZHMgYm90aCBpZiAkWF5cdG9wIFgkIGlzIHNpbmd1bGFyCgotIEZvciBoaWdoIGRpbWVuc2lvbmFsIGRhdGEgJHA+Pm4kICBkZXNpZ24gbWF0cml4ICRYJCBpcyBuZXZlciBmdWxsIHJhbmsuIAoKIyMgQSBwcmFjdGljZSBvZiBsaW5lYXIgbW9kZWwgZm9yIGNsYXNzaWZpY2F0aW9uCgotIE9uZSBvZiB0aGUgbW9zdCBjb21tb24gZGF0YXNldHMgaXMgdGhlICoqTU5JU1QqKiBEaWdpdHMgZGF0YXNldC4gSXQgaXMgY29tcG9zZWQgb2YgbW9ub2Nocm9tZSBkaWdpdHMgb2YgJDI4XHRpbWVzIDI4JCBwaXhlbHMgYW5kIGxhYmVscyBpbmRpY2F0aW5nIGVhY2ggZGlnaXQuIAoKIVtdKGRpZ2l0c19zZXBhcmF0ZS5wbmcpCgotIFRoZXJlIGFyZSAkNjAsMDAwJCBkaWdpdHMgdGhhdCBhcmUgY2FsbGVkIHRoZSB0cmFpbmluZyBzZXQgYW5kICQxMCwwMDAkIGFkZGl0aW9uYWwgZGlnaXRzIHRoYXQgYXJlIGNhbGxlZCB0aGUgdGVzdCBzZXQuCgoKLSBUaGUgaW5wdXQgcGl4ZWxzIGFyZSBncmV5c2NhbGUsIHdpdGggYSB2YWx1ZSBvZiAwLjAgcmVwcmVzZW50aW5nIHdoaXRlLCBhIHZhbHVlIG9mIDEuMCByZXByZXNlbnRpbmcgYmxhY2ssIGFuZCBpbiBiZXR3ZWVuIHZhbHVlcyByZXByZXNlbnRpbmcgZ3JhZHVhbGx5IGRhcmtlbmluZyBzaGFkZXMgb2YgZ3JleS4KCgotIEZpcnN0LCB3ZSBuZWVkIHRvIGRvd25sb2FkIGFuZCBkZWNvbXByZXNzIHRoZSBmb2xsb3dpbmcgZmlsZXMuIFRoZWlyIGZvcm1hdCBpcyBkZXNjcmliZWQgb24gdGhlIHdlYnNpdGUuIAoKKiBbdHJhaW5pbmcgc2V0IGltYWdlcyAoOTkxMjQyMiBieXRlcyldKGh0dHA6Ly95YW5uLmxlY3VuLmNvbS9leGRiL21uaXN0L3RyYWluLWltYWdlcy1pZHgzLXVieXRlLmd6KQoqIFt0cmFpbmluZyBzZXQgbGFiZWxzICgyODg4MSBieXRlcyldKGh0dHA6Ly95YW5uLmxlY3VuLmNvbS9leGRiL21uaXN0L3RyYWluLWxhYmVscy1pZHgxLXVieXRlLmd6KQoqIFt0ZXN0IHNldCBpbWFnZXMgKDE2NDg4NzcgYnl0ZXMpXShodHRwOi8veWFubi5sZWN1bi5jb20vZXhkYi9tbmlzdC90MTBrLWltYWdlcy1pZHgzLXVieXRlLmd6KQoqIFt0ZXN0IHNldCBsYWJlbHMgKDQ1NDIgYnl0ZXMpXShodHRwOi8veWFubi5sZWN1bi5jb20vZXhkYi9tbmlzdC90MTBrLWxhYmVscy1pZHgxLXVieXRlLmd6KQoKV2UgdXNlIFIgdG8gZXh0cmFjdCB0aGUgaW5mb3JtYXRpb24gZnJvbSB0aGVzZSBmaWxlcy4KCmBgYHtyLHRpZHk9VFJVRSx0aWR5Lm9wdHMgPSBsaXN0KGJsYW5rID0gRkFMU0UsIHdpZHRoLmN1dG9mZiA9IDYwKSxjYWNoZT1UUlVFfQpmaWxlX3RyYWluaW5nX3NldF9pbWFnZSA8LSAidHJhaW4taW1hZ2VzLmlkeDMtdWJ5dGUiCmZpbGVfdHJhaW5pbmdfc2V0X2xhYmVsIDwtICJ0cmFpbi1sYWJlbHMuaWR4MS11Ynl0ZSIKZmlsZV90ZXN0X3NldF9pbWFnZSA8LSAidDEway1pbWFnZXMuaWR4My11Ynl0ZSIKZmlsZV90ZXN0X3NldF9sYWJlbCA8LSAidDEway1sYWJlbHMuaWR4MS11Ynl0ZSIKCmV4dHJhY3RfaW1hZ2VzIDwtIGZ1bmN0aW9uKGZpbGUsIG5iaW1hZ2VzID0gTlVMTCkgewogIGlmIChpcy5udWxsKG5iaW1hZ2VzKSkgeyAjIFdlIGV4dHJhY3QgYWxsIGltYWdlcwogICAgbmJpbWFnZXMgPC0gYXMubnVtZXJpYyhwYXN0ZSgiMHgiLCBwYXN0ZShyZWFkQmluKGZpbGUsICJyYXciLCBuID0gOClbNTo4XSwgY29sbGFwc2UgPSAiIiksIHNlcCA9ICIiKSkKICB9CiBuYnJvd3MgPC0gYXMubnVtZXJpYyhwYXN0ZSgiMHgiLCBwYXN0ZShyZWFkQmluKGZpbGUsICJyYXciLCBuID0gMTIpWzk6MTJdLCBjb2xsYXBzZSA9ICIiKSwgc2VwID0gIiIpKQogbmJjb2xzIDwtIGFzLm51bWVyaWMocGFzdGUoIjB4IiwgcGFzdGUocmVhZEJpbihmaWxlLCAicmF3IiwgbiA9IDE2KVsxMzoxNl0sIGNvbGxhcHNlID0gIiIpLCBzZXAgPSAiIikpCiByYXcgPC0gcmVhZEJpbihmaWxlLCAicmF3IiwgbiA9IG5iaW1hZ2VzICogbmJyb3dzICogbmJjb2xzICsgMTYpWy0oMToxNildCnJldHVybihhcnJheShhcy5udW1lcmljKHBhc3RlKCIweCIsIHJhdywgc2VwPSIiKSksIGRpbSA9IGMobmJjb2xzLCBuYnJvd3MsIG5iaW1hZ2VzKSkpCn0KCmV4dHJhY3RfbGFiZWxzIDwtIGZ1bmN0aW9uKGZpbGUpIHsKIG5iaXRlbSA8LSBhcy5udW1lcmljKHBhc3RlKCIweCIsIHBhc3RlKHJlYWRCaW4oZmlsZSwgInJhdyIsIG4gPSA4KVs1OjhdLCBjb2xsYXBzZSA9ICIiKSwgc2VwID0gIiIpKQogcmF3IDwtIHJlYWRCaW4oZmlsZSwgInJhdyIsIG4gPSBuYml0ZW0gKyA4KVstKDE6OCldCnJldHVybihhcy5udW1lcmljKHBhc3RlKCIweCIsIHJhdywgc2VwPSIiKSkpCn0KCmltYWdlc190cmFpbmluZ19zZXQgPC0gZXh0cmFjdF9pbWFnZXMoZmlsZV90cmFpbmluZ19zZXRfaW1hZ2UsIDYwMDAwKQppbWFnZXNfdGVzdF9zZXQgPC0gZXh0cmFjdF9pbWFnZXMoZmlsZV90ZXN0X3NldF9pbWFnZSwgMTAwMDApCmxhYmVsc190cmFpbmluZ19zZXQgPC0gZXh0cmFjdF9sYWJlbHMoZmlsZV90cmFpbmluZ19zZXRfbGFiZWwpCmxhYmVsc190ZXN0X3NldCA8LSBleHRyYWN0X2xhYmVscyhmaWxlX3Rlc3Rfc2V0X2xhYmVsKQoKbGFiZWxzX3RyYWluaW5nX3NldFsxOjEwXQojIHBhcihhc2sgPSBUUlVFKQpwYXIobWZyb3c9YygyLDIpKQpmb3IgKGkgaW4gMTo0KSBpbWFnZShhcy5tYXRyaXgocmV2KGFzLmRhdGEuZnJhbWUoaW1hZ2VzX3RyYWluaW5nX3NldFssLGldKSkpLCBjb2wgPSBncmF5KCgyNTU6MCkvMjU2KSkKCmBgYAoKLSBFYWNoIHRyYWluaW5nIGlucHV0ICRcbWF0aGJme3h9JCBpcyBhICQyOFx0aW1lcyAyOCA9IDc4NCQtZGltZW5zaW9uYWwgdmVjdG9yLiBFYWNoIGVudHJ5IGluIHRoZSB2ZWN0b3IgcmVwcmVzZW50cyB0aGUgZ3JleSB2YWx1ZSBmb3IgYSBzaW5nbGUgcGl4ZWwgaW4gdGhlIGltYWdlLgoKCi0gV2UnbGwgZGVub3RlIHRoZSBjb3JyZXNwb25kaW5nIF9kZXNpcmVkXyBvdXRwdXQgYnkgJFxtYXRoYmZ7eX0gPSB5KFxtYXRoYmZ7eH0pJCwgd2hlcmUgJFxtYXRoYmZ7eX0kIGlzIGEgMTAtZGltZW5zaW9uYWwgdmVjdG9yLiBGb3IgZXhhbXBsZSwgaWYgYSBwYXJ0aWN1bGFyIHRyYWluaW5nIGltYWdlLCAkXG1hdGhiZnt4fSQsIGRlcGljdHMgYSA2LCB0aGVuICR5KFxtYXRoYmZ7eH0pPSgwLDAsMCwwLDAsMCwxLDAsMCwwKVx0b3AkIGlzIHRoZSBkZXNpcmVkIG91dHB1dCBmcm9tIHRoZSBuZXR3b3JrLgoKCgotICBXZSBjb25zaWRlciBlYWNoIGltYWdlIGFzIGEgdmVjdG9yIGFuZCBvYnRhaW4gZGlmZmVyZW50IGxlYXN0IHNxdWFyZXMgZXN0aW1hdG9ycyBmb3IgZWFjaCB0eXBlIG9mIGRpZ2l0LiBGb3IgZGlnaXQgJFxlbGxcaW57MCxcbGRvdHMsOX0kIHdlIGNvbGxlY3QgYWxsIHRoZSB0cmFpbmluZyBkYXRhIHZlY3RvcnMsIHdpdGggJHlfaT1cZWxsJC4gVGhlbiBmb3IgZWFjaCBzdWNoICRpJCwgd2Ugc2V0ICR5X2kgPSArMSQgYW5kIGZvciBhbGwgb3RoZXIgJGkkIHdpdGggJHlfaVxuZXEgXGVsbCQsIHdlIHNldCAkeV9pID0g4oiSMSQuIAoKLSBUaGlzIGxhYmVscyBvdXIgZGF0YSBhcyBjbGFzc2lmeWluZyAqKl95ZXMgZGlnaXRfKiogdnMuICoqX25vdCBkaWdpdF8qKi4gQ2FsbCB0aGlzIHZlY3RvciBvZiDiiJIxIGFuZCArMSB2YWx1ZXMgJHleeyhcZWxsKX0kIGZvciBldmVyeSBkaWdpdCAkXGVsbCQuIAoKLSBXZSB0aGVuIGNvbXB1dGUsCiQkXGJldGFeeyhcZWxsKX09KFheVFgpXnstMX1YXlx0b3AgeV57XGVsbH1cIFwgXCBcIFwgXHRleHRybXtmb3J9IFwgXCBcIFxlbGw9MCxcbGRvdHMsOSQkCndoZXJlICRYJCBpcyB0aGUgJDYwLDAwMFx0aW1lcyA3ODQkIGRlc2lnbiBtYXRyaXggYXNzb2NpYXRlZCB3aXRoIHRoZSAkNjAsMDAwJCBpbWFnZXMuCgpOb3cgZm9yIGV2ZXJ5IGltYWdlICRpJCwgdGhlIGlubmVyIHByb2R1Y3QgJFxiZXRhXnsoXGVsbCl9LlxtYXRoYmZ7eH1eXHRvcF9pJCB5aWVsZHMgYW4gZXN0aW1hdGUgb2YgaG93IGxpa2VseSB0aGlzIGltYWdlIGlzIG9mIHRoZSBkaWdpdCAkXGVsbCQuIEEgdmVyeSBoaWdoIHZhbHVlIGluZGljYXRlZCBhIGhpZ2ggbGlrZWxpaG9vZCBhbmQgYSBsb3cgdmFsdWUgaXMgYSBsb3cgbGlrZWxpaG9vZC4gV2UgdGhlbiBjbGFzc2lmeSBhbiBhcmJpdHJhcnkgaW1hZ2UgJFx0aWxkZXtcbWF0aGJmIHh9JCBieSAKCgpcYmVnaW57ZXFuYXJyYXl9ClxoYXR7eX0oXHRpbGRle3h9KSA9IFx0ZXh0cm17YXJnIG1heCB9IFxiZXRhXnsoXGVsbCl9Llx0aWxkZXt4fV5cdG9wIFwgXCBcIFwgXCBcIFwgICgxKQpcZW5ke2VxbmFycmF5fQoKCi0gT2JzZXJ2ZSB0aGF0IGR1cmluZyB0aGUgdHJhaW5pbmcsIHRoaXMgY2xhc3NpZmllciBvbmx5IHJlcXVpcmVzIGNhbGN1bGF0aW5nICQoWF5UWCleey0xfVheVCQgb25jZS4gSXQgdGhlbiBvbmx5IG5lZWRzIHRvIHJlbWVtYmVyIDEwIHZlY3RvcnMgJFxiZXRhXzAsXGxkb3RzLFxiZXRhXzkkLiBUaGVuIGJhc2VkIG9uIHRoZXNlIDEwIHZlY3RvcnMsIGEgZGVjaXNpb24gcnVsZSBpcyB2ZXJ5IHNpbXBsZSB0byBleGVjdXRlIGluICgxKS4KCgotIENyZWF0ZSBEZXNpZ24gbWF0cml4IGFuZCBvdXRjb21lIHJlc3BvbnNlcwoKYGBge3J9CnZlY3Rvcml6ZWRfcmVzdWx0IDwtIGZ1bmN0aW9uKGopIHsKICBlIDwtIGFzLm1hdHJpeChyZXAoMCwgMTApKQogIGVbaiArIDFdIDwtIDEKICByZXR1cm4oZSkKfQoKWHRyYWluIDwtIG1hdHJpeCgwLG5yb3c9NjAwMDAsbmNvbD03ODQpCll0cmFpbiA8LSBtYXRyaXgoMCxucm93PTYwMDAwLG5jb2w9MTApCmZvciAoaSBpbiAxOjYwMDAwKSB7CiAgWHRyYWluW2ksXSA8LSBhcy52ZWN0b3IoaW1hZ2VzX3RyYWluaW5nX3NldFssLGldKSAvIDI1NgogIFl0cmFpbltpLF0gPC0gdCh2ZWN0b3JpemVkX3Jlc3VsdChsYWJlbHNfdHJhaW5pbmdfc2V0W2ldKSkKfQpZdHJhaW5bd2hpY2goWXRyYWluPT0wKV0gPC0gLTEKClh0ZXN0IDwtIG1hdHJpeCgwLG5yb3c9MTAwMDAsbmNvbD03ODQpCll0ZXN0IDwtIG1hdHJpeCgwLG5yb3c9MTAwMDAsbmNvbD0xMCkKZm9yIChpIGluIDE6MTAwMDApIHsKICBYdGVzdFtpLF0gPC0gYXMudmVjdG9yKGltYWdlc190ZXN0X3NldFssLGldKSAvIDI1NgogIFl0ZXN0W2ksXSA8LSB0KHZlY3Rvcml6ZWRfcmVzdWx0KGxhYmVsc190ZXN0X3NldFtpXSkpCn0KYGBgCgotIENvbXB1dGUgdGhlIGtleSBlbGVtZW50ICQoWF5UWCleey0xfVheVCQuIEFzICQoWF5UWCkkIGlzIHNpbmd1bGFyLCB3ZSB1c2UgdGhlIE1vb3JlLVBlbnJvc2UgZ2VuZXJhbGl6ZWQgaW52ZXJzZSBtYXRyaXggb2YgJFgkIHRocm91Z2ggdGhlIFx0ZXh0dHR7Z2ludn0gZnVuY3Rpb24gZnJvbSB0aGUgXHRleHR0dHtNQVNTfSBSIHBhY2thZ2U6IAoKYGBge3IsY2FjaGU9VFJVRX0KbGlicmFyeShNQVNTKQptYXQgPC0gZ2ludihYdHJhaW4pCmBgYAoKLSBFc3RpbWF0ZSB0aGUgMTAgbGluZWFyIGNsYXNzaWZpZXIgbW9kZWxzIAoKYGBge3J9Cm1vZGVsIDwtIG1hdHJpeCgwLG5yb3c9Nzg0LG5jb2w9MTApCmZvcihpIGluIDE6MTApewptb2RlbFssaV0gPC0gbWF0JSolbWF0cml4KFl0cmFpblssaV0sbmNvbD0xKSAgCn0KYGBgCgotIENyZWF0ZSB0aGUgcHJlZGljdGlvbiBmdW5jdGlvbiBmb3IgdGhlIGxpbmVhciBjbGFzc2lmaWVyCgpgYGB7cn0KCnByZWQubW9kZWwgPC0gZnVuY3Rpb24oeCxYdGVzdD1YdGVzdCl7c3VtKHgqWHRlc3QpfQoKbGluZWFyLmNsYXNzIDwtIGZ1bmN0aW9uKG1vZGVsLFh0ZXN0KXsKICByZXMgPC0gYXBwbHkobW9kZWwsTUFSR0lOPTIsRlVOPXByZWQubW9kZWwsWHRlc3Q9WHRlc3QpCiAgcHJlZCA8LSB3aGljaC5tYXgocmVzKS0xCiAgcmV0dXJuKHByZWQpCn0KYGBgCgotIFBlcmZvcm1hbmNlIG9uIHRoZSB0ZXN0IGRhdGEgCgpgYGB7cn0KcmVzdWx0IDwtIDAKcmVzIDwtIHJlcCgwLDEwMDAwKQpmb3IgKGkgaW4gMToxMDAwMCl7Clh0ZXN0MSA8LSAoYXMudmVjdG9yKGltYWdlc190ZXN0X3NldFssLGldKSAvIDI1NikKcmVzaSA8LSBsaW5lYXIuY2xhc3MobW9kZWwsWHRlc3Q9WHRlc3QxKQpyZXNbaV0gPC0gcmVzaQppZihhYnMocmVzaS1sYWJlbHNfdGVzdF9zZXRbaV0pPDAuNSkgcmVzdWx0IDwtIHJlc3VsdCArMQp9CmFjY3VyYWN5IDwtIHJlc3VsdC8xMDAwMAphY2N1cmFjeQpgYGAKCi0gQ29uZnVzaW9uIE1hdHJpeAoKYGBge3J9CmxpYnJhcnkoY2FyZXQpCmNhcmV0Ojpjb25mdXNpb25NYXRyaXgoZmFjdG9yKHJlcyksZmFjdG9yKGxhYmVsc190ZXN0X3NldCkpJHRhYmxlCmBgYAoKCi0gV2UgaGF2ZSB1c2VkIHRoZSBgYG9uZSB2cy5cIGFsbGBgIChhbHNvIGtub3duIGFzIGBgb25lIHZzLlwgcmVzdGBgKSBzdHJhdGVneSB1c2luZyAqKkJpbmFyeSBjbGFzc2lmaWNhdGlvbioqIGZvciAqKm11bHRpLWNsYXNzIGNsYXNzaWZpY2F0aW9uIHByb2JsZW0qKiAoc2VlIGxhdGVyKQoKLSBTZWNvbmQgb3B0aW9uOiAqKm9uZSB2cy5cIG9uZSoqIHN0cmF0ZWd5LiBXZSBoYXZlICRLKEstMSkvMiQgYmluYXJ5IGNsYXNzaWZpZXJzIGRlbm90ZWQgJHtmfV97e1x0aGV0YX1fe2ksan19KHgpJCBmb3IgYWxsICRpLGogPSAxLFxsZG90cyxLJCBzdWNoIHRoYXQgJGkgXG5lcSBqJC4gSGVyZSB0aGUgJChpLGopdGgkIGNsYXNzaWZpZXIgZGlzY3JpbWluYXRlcyBiZXR3ZWVuIHRoZSBsYWJlbCBiZWluZyBvZiBpbmRleCAkaSQgb3IgaW5kZXggJGokCgotIFRoZSAqKm9uZSB2cy4gYWxsKiogb3IgKipvbmUgdnMuIG9uZSoqIHN0cmF0ZWdpZXMgY2Fycnkgb3V0IHByZWRpY3Rpb24gdmlhLAoKXFsKXHdpZGVoYXR7XGNhbCBZfSA9IApcYmVnaW57Y2FzZXN9Clx0ZXh0cm17YXJnbWF4fV97aT0xLFxsZG90cyxLfSB7Zn1fe3tcdGhldGF9X2l9KHgpICYgXHFxdWFkIFx0ZXh0e2luIGNhc2Ugb2Ygb25lIHZzLiBhbGx9LCBcXApcdGV4dHJte2FyZ21heH1fe2k9MSxcbGRvdHMsS30gXHN1bV97aiBcbmVxIGl9IFx0ZXh0e3NpZ259XGJpZygge2Z9X3t7XHRoZXRhfV97aSxqfX0oeCkgXGJpZykmIFxxcXVhZCBcdGV4dHtpbiBjYXNlIG9mIG9uZSB2cy4gb25lfS4gXFwKXGVuZHtjYXNlc30KXF0KCi0gVGhlIGlkZWEgb2YgdGhlIG9uZSB2cy4gb25lIGNsYXNzaWZpZXIgaXMgdG8gcGljayB0aGUgbGFiZWwgJGkkIHRoYXQgd2hlbiBjb21wYXJlZCB0byB0aGUgb3RoZXIgJEstMSQgbGFiZWxzLCB3YXMgY2hvc2VuIG1vc3Qgb2Z0ZW4uIAoKCiMjIE1vZGVsIENob2ljZSwgVW5kZXItZml0dGluZywgYW5kIE92ZXItZml0dGluZwoKLSBUcmFkZW9mZnMgb2YgbW9kZWwgY29tcGxleGl0eSB1c2luZyBsaW5lYXIgbW9kZWxzIHdpdGggcG9seW5vbWlhbCBmZWF0dXJlcyAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse3BvbHl9CnkgPSBcYmV0YV8wICsgXGJldGFfMSB4ICsgXGJldGFfMiB4XjIgKyBcbGRvdHMgKyBcYmV0YV9rIHheaysgXGVwc2lsb24KXGVuZHtlcXVhdGlvbn0KCi0gJFxtYXRoY2Fse019X2skIG1lYW5zIHBvbHlub21pYWwgbW9kZWwgb2Ygb3JkZXIgJGskIAoKLSBIZW5jZSAkXG1hdGhjYWx7TX1fMCQgaXMgdGhlIGNvbnN0YW50IG1vZGVsLCAgJFxtYXRoY2Fse019XzEkIGlzIHRoZSBzaW1wbGUgbGluZWFyIG1vZGVsLCAkXG1hdGhjYWx7TX1fMiQgaXMgdGhlIHF1YWRyYXRpYyBtb2RlbCwgYW5kIHNvIG9uLiAKCi0gTW9kZWwgIGNvbXBsZXhpdHkgY29ycmVzcG9uZHMgdG8gdGhlIGRlZ3JlZSBvZiB0aGUgcG9seW5vbWlhbCBtb2RlbC4gCgotICAkXG1hdGhjYWx7RH1fe1x0ZXh0e3RyYWlufX0kIG9mIHNpemUgJG5fe1x0ZXh0e3RyYWlufX09MTAkLiAKCmBgYHtyLGVjaG89RkFMU0V9CnNldC5zZWVkKDExKQp4IDwtIHNlcSgwLDEsbGVuZ3RoPTEwKQp5IDwtIHNpbigyKnBpKngpLWNvcygyKnBpKngpK3Jub3JtKDEwLDAsMC4yKQpteWRhdGEgPC0gZGF0YS5mcmFtZSh5PXkseD14KQpzYXZlKG15ZGF0YSxmaWxlPSJkYXRhLXBvbHkuUmRhdGEiKQpsaWJyYXJ5KGdncGxvdDIpCmdncGxvdChteWRhdGEsIGFlcyh4LCB5KSkgKyAKICBnZW9tX3BvaW50KCkgCmBgYAoKLSBMZXQgdHJ5IGRpZmZlcmVudCBtb2RlbCAkXG1hdGhjYWx7TX1fayQuCgoKYGBge3J9CmxvYWQoImRhdGEtcG9seS5SZGF0YSIpCnkgPC0gbXlkYXRhJHkKeCA8LSBteWRhdGEkeAptb2RlbDAgPC0gZ2xtKHl+MSkKbW9kZWwxIDwtIGdsbSh5fnBvbHkoeCwxKSkKbW9kZWwyIDwtIGdsbSh5fnBvbHkoeCwyKSkKbW9kZWwzIDwtIGdsbSh5fnBvbHkoeCwzKSkKbW9kZWw0IDwtIGdsbSh5fnBvbHkoeCw0KSkKbW9kZWw1IDwtIGdsbSh5fnBvbHkoeCw1KSkKbW9kZWw2IDwtIGdsbSh5fnBvbHkoeCw2KSkKbW9kZWw3IDwtIGdsbSh5fnBvbHkoeCw3KSkKbW9kZWw4IDwtIGdsbSh5fnBvbHkoeCw4KSkKbW9kZWw5IDwtIGdsbSh5fnBvbHkoeCw5KSkKCiMgTXVjaCBiZXR0ZXIKbW9kZWwubGlzdCA8LSB2ZWN0b3IoImxpc3QiLCBsZW5ndGggPSAxMCkKbW9kZWwubGlzdFtbMV1dIDwtIGdsbSh5fjEpCmZvciAoaSBpbiAxOjkpewogIGZvcm11bGEgPC0gYXMuZm9ybXVsYShwYXN0ZSgieSB+IHBvbHkoeCwiLGksIikiLHNlcD0iIikpCiAgbW9kZWwubGlzdFtbaSsxXV0gPC0gZ2xtKGZvcm11bGEpIAp9CgoKCm15LmZvcm11bGEgPC0geSB+IDEKcDAgPC0gZ2dwbG90KG15ZGF0YSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9zbW9vdGgobWV0aG9kID0gImxtIiwgc2UgPSBGQUxTRSwgCiAgICAgICAgICAgICAgZm9ybXVsYSA9IG15LmZvcm11bGEsIAogICAgICAgICAgICAgIGNvbG91ciA9ICJyZWQiKSsKICBsYWJzKHRpdGxlPWVsZW1lbnRfdGV4dCgiUG9seW5vbWlhbCBmaXQgd2l0aCBrPTAiKSkrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKSArIHRoZW1lX2J3KCkKCgpteS5mb3JtdWxhIDwtIHkgfiBwb2x5KHgsIDEsIHJhdyA9IFRSVUUpCgpwMSA8LSBnZ3Bsb3QobXlkYXRhLCBhZXMoeCwgeSkpICsgCiAgZ2VvbV9wb2ludCgpICsKICBnZW9tX3Ntb290aChtZXRob2QgPSAibG0iLCBzZSA9IEZBTFNFLCAKICAgICAgICAgICAgICBmb3JtdWxhID0gbXkuZm9ybXVsYSwgCiAgICAgICAgICAgICAgY29sb3VyID0gInJlZCIpKwogIGxhYnModGl0bGU9ZWxlbWVudF90ZXh0KCJQb2x5bm9taWFsIGZpdCB3aXRoIGs9MSIpKSsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpICsgdGhlbWVfYncoKQoKbXkuZm9ybXVsYSA8LSB5IH4gcG9seSh4LCAzLCByYXcgPSBUUlVFKQoKcDMgPC0gZ2dwbG90KG15ZGF0YSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9zbW9vdGgobWV0aG9kID0gImxtIiwgc2UgPSBGQUxTRSwgCiAgICAgICAgICAgICAgZm9ybXVsYSA9IG15LmZvcm11bGEsIAogICAgICAgICAgICAgIGNvbG91ciA9ICJyZWQiKSsKICBsYWJzKHRpdGxlPWVsZW1lbnRfdGV4dCgiUG9seW5vbWlhbCBmaXQgd2l0aCBrPTMiKSkrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKSsgdGhlbWVfYncoKQoKCm15LmZvcm11bGEgPC0geSB+IHBvbHkoeCwgOSwgcmF3ID0gVFJVRSkKCgpwOSA8LSBnZ3Bsb3QobXlkYXRhLGFlcyh4LCB5PXkpKSArIAogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9zbW9vdGgobWV0aG9kID0gImxtIiwgc2UgPSBGQUxTRSwgCiAgICAgICAgICAgICAgZm9ybXVsYSA9IG15LmZvcm11bGEsIAogICAgICAgICAgICAgIGNvbG91ciA9ICJyZWQiKSsKICBsYWJzKHRpdGxlPWVsZW1lbnRfdGV4dCgiUG9seW5vbWlhbCBmaXQgd2l0aCBrPTkiKSkrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKSArIHRoZW1lX2J3KCkKCmxpYnJhcnkoZ2dwdWJyKQpnZ2FycmFuZ2UocDAscDEscDMscDksbmNvbCA9IDIsIG5yb3cgPSAyKQpgYGAKCi0gSXQgaXMgb2J2aW91cyB0aGF0IGFzICRrJCBpbmNyZWFzZXMgdHJhaW5pbmcgZml0IGltcHJvdmVzLiAKCi0gRXZhbHVhdGUgdGhlIHBlcmZvcm1hbmNlIG9mIHRoZSBtb2RlbCB1c2luZyBhIHBlcmZvcm1hbmNlIG1lYXN1cmUgJHtcY2FsIFB9JCAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmUtdHJhaW4tdHJhaW59CntFfV97XHRleHR7dHJhaW59fSAgPSBcZnJhY3sxfXtuX3tcdGV4dHt0cmFpbn19fVxzdW1feyh4LHkpIFxpbiBcbWF0aGNhbHtEfV97XHRleHR7dHJhaW59fX0gIHtcY2FsIFB9IFxiaWcoXHdpZGVoYXR7eX0oeCBcLCA7IFwsIFxtYXRoY2Fse0R9e1x0ZXh0e3RyYWlufX0pLFwsIHlcYmlnKSwKXGVuZHtlcXVhdGlvbn0KCi0gSGVyZSBuYXR1cmFsIHRvIHVzZSAke1xjYWwgUH0oXGJpZyhcd2lkZWhhdHt5fSh4IFwsIDsgXCwgXG1hdGhjYWx7RH1fe1x0ZXh0e3RyYWlufX0pLFwsIHlcYmlnKSk9KFx3aWRlaGF0e3l9LXkpXjIkCgpgYGB7cn0KUk1TRSA8LSBmdW5jdGlvbihtb2RlbCxkYXRhWFkpewogIHByZWQgPC0gcHJlZGljdC5nbG0obW9kZWwsbmV3ZGF0YT1kYXRhLmZyYW1lKHg9ZGF0YVhZJFgpKQogIFJNU0UgPC0gbWVhbigocHJlZC1kYXRhWFkkWSkqKjIpCiAgcmV0dXJuKFJNU0UpCn0KCmRhdGEudHJhaW4gPC0gZGF0YS5mcmFtZShYPXgsWT15KQoKUk1TRS5yZXN1bHQgPC0gbWF0cml4KE5BLG5yb3c9MTAsbmNvbD0yKQpmb3IoaSBpbiAxOjEwKXsKICBtb2RlbCA8LSBtb2RlbC5saXN0W1tpXV0KICBSTVNFLnJlc3VsdFtpLF0gPC0gYyhpLTEsUk1TRShtb2RlbCxkYXRhLnRyYWluKSkKfQoKZGF0YS5yZXN1bHQgPC0gYXMuZGF0YS5mcmFtZShSTVNFLnJlc3VsdCkKY29sbmFtZXMoZGF0YS5yZXN1bHQpIDwtIGMoIk0iLCJUcmFpbiIpCm15ZGF0YSA8LSBkYXRhLmZyYW1lKE1vZGVsPWRhdGEucmVzdWx0JE0sUGVyZm9ybWFuY2U9ZGF0YS5yZXN1bHQkVHJhaW4sR3JvdXA9cmVwKCJUcmFpbiIsZWFjaD0xMCksY29sb3I9cmVwKCJyZWQiLGVhY2g9MTApKQoKCgpsaW5ldHlwZSA9IGMoJ3NvbGlkJywgJ3NvbGlkJykKTGVnZW5kVGl0bGUgPSAiIgpwIDwtIGdncGxvdChteWRhdGEsIGFlcyhNb2RlbCxQZXJmb3JtYW5jZSwgZ3JvdXAgPSBHcm91cCxjb2xvcj1jb2xvcikpKwogIGdlb21fbGluZShhZXMoZ3JvdXAgPSBHcm91cCxjb2xvcj1jb2xvcikpKyMsInJlZCIpKSArCiAgc2NhbGVfY29sb3JfaWRlbnRpdHkobGFiZWxzID0gYyhibHVlID0gImJsdWUiLHJlZCA9ICJyZWQiKSkrCiAgI3NjYWxlX2xpbmV0eXBlX21hbnVhbChuYW1lID0gTGVnZW5kVGl0bGUsIHZhbHVlcyA9IGxpbmV0eXBlKSArCiAgc2NhbGVfeF9jb250aW51b3VzKG5hbWU9Ik1vZGVsIChrKSIsYnJlYWtzPTA6OSxsYWJlbHM9MDo5KSsKICBzY2FsZV95X2NvbnRpbnVvdXMobmFtZT0iTWVhbiBTcXVhcmUgRXJyb3IiKSsKICB0aGVtZV9idygpICsKICBhbm5vdGF0ZShnZW9tPSJ0ZXh0IiwgeD03LjUsIHk9MSwgbGFiZWw9IkVfdHJhaW4gIixjb2xvcj0icmVkIikrCiAgYW5ub3RhdGUoInNlZ21lbnQiLCB4ID0gNi42LCB4ZW5kID0gNywgeSA9IDEsIHllbmQgPSAxLAogICAgICAgICBjb2xvdXIgPSAicmVkIikKcAoKYGBgCgotIEl0IGlzIG9idmlvdXMgdGhhdCBhcyAkayQgaW5jcmVhc2VzIHRyYWluaW5nIGZpdCBpbXByb3Zlcy4gCgotIEh5cG90aGV0aWNhbCBleGFtcGxlOiAgd2Uga25vdyB0aGUgdW5kZXJseWluZyBwcm9jZXNzIHdpdGggcHJvYmFiaWxpdHkgbGF3ICRQKHgseSkkIHVzZWQgZm9yIHB1cnBvc2VzIG9mIHNpbXVsYXRpb24gb2Ygc3ludGhldGljIGRhdGEKCi0gV2UgbWF5IHNhbXBsZSBhcyBtYW55ICQoeF5cc3Rhcix5XlxzdGFyKSQgcGFpcnMgYXMgd2Ugd2lzaCwgdG8gb2J0YWluIHRoZSBwZXJmb3JtYW5jZSBtZWFzdXJlIGZvciBgYHVuc2VlbmBgIGRhdGEgJEVfe1x0ZXh0e3Vuc2Vlbn19JC4KCi0gICQxMCwwMDAkIHJlcGV0aXRpb25zIGZvciBlYWNoICRrJCwgZWFjaCB0aW1lIHdpdGggdGhlIGZpeGVkIG1vZGVsIGJhc2VkIG9uIG91ciBzaW5nbGUgYXZhaWxhYmxlIGRhdGFzZXQuCgpgYGB7cn0Kc2V0LnNlZWQoMTEyMykKdGVzdHggPC0gc2VxKDAsMSxsZW5ndGg9MTAwMDApCnRlc3R5IDwtIHNpbigyKnBpKnRlc3R4KS1jb3MoMipwaSp0ZXN0eCkrcm5vcm0oMTAwMDAsMCwwLjIpCmRhdGEudGVzdCA8LSBkYXRhLmZyYW1lKFg9dGVzdHgsWT10ZXN0eSkKCgpSTVNFLnJlc3VsdCA8LSBtYXRyaXgoTkEsbnJvdz0xMCxuY29sPTMpCmZvcihpIGluIDE6MTApewogIG1vZGVsIDwtIG1vZGVsLmxpc3RbW2ldXQogIFJNU0UucmVzdWx0W2ksXSA8LSBjKGktMSxSTVNFKG1vZGVsLGRhdGEudHJhaW4pLFJNU0UobW9kZWwsZGF0YS50ZXN0KSkKfQoKCmNvbG5hbWVzKFJNU0UucmVzdWx0KSA8LSBjKCJNIiwiVHJhaW4iLCJUZXN0IikKZGF0YS5yZXN1bHQgPC0gYXMuZGF0YS5mcmFtZShSTVNFLnJlc3VsdCkKY29sbmFtZXMoUk1TRS5yZXN1bHQpIDwtIGMoIk0iLCJUcmFpbiIsIlRlc3QiKQpteWRhdGEgPC0gZGF0YS5mcmFtZShNb2RlbD1yZXAoZGF0YS5yZXN1bHQkTSwyKSxQZXJmb3JtYW5jZT1jKGRhdGEucmVzdWx0JFRyYWluLGRhdGEucmVzdWx0JFRlc3QpLEdyb3VwPXJlcChjKCJUcmFpbiIsIlByb2R1Y3Rpb24iKSxlYWNoPTEwKSxjb2xvcj1yZXAoYygicmVkIiwiYmxhY2siKSxlYWNoPTEwKSkKCmxpbmV0eXBlID0gYygnc29saWQnLCAnc29saWQnKQpMZWdlbmRUaXRsZSA9ICIiCnAgPC0gZ2dwbG90KG15ZGF0YSwgYWVzKE1vZGVsLFBlcmZvcm1hbmNlLCBncm91cCA9IEdyb3VwLGNvbG9yPWNvbG9yKSkrCiAgZ2VvbV9saW5lKGFlcyhncm91cCA9IEdyb3VwLGNvbG9yPWNvbG9yKSkrIywicmVkIikpICsKICBzY2FsZV9jb2xvcl9pZGVudGl0eShsYWJlbHMgPSBjKGJsdWUgPSAiYmx1ZSIscmVkID0gInJlZCIpKSsKICBzY2FsZV94X2NvbnRpbnVvdXMobmFtZT0iTW9kZWwgKGspIixicmVha3M9MDo5LGxhYmVscz0wOjkpKwogIHNjYWxlX3lfY29udGludW91cyhuYW1lPSJNZWFuIFNxdWFyZSBFcnJvciIpKwogIHRoZW1lX2J3KCkgKwogIGFubm90YXRlKGdlb209InRleHQiLCB4PTcuNSwgeT0xLCBsYWJlbD0iRV90cmFpbiIsIHBhcnNlPVRSVUUKICAgICAgICAgICAgICxjb2xvcj0icmVkIikrCiAgYW5ub3RhdGUoInNlZ21lbnQiLCB4ID0gNi42LCB4ZW5kID0gNywgeSA9IDEsIHllbmQgPSAxLAogICAgICAgICBjb2xvdXIgPSAicmVkIikrCiAgYW5ub3RhdGUoZ2VvbT0idGV4dCIsIHg9Ny42LCB5PTAuOTUsIGxhYmVsPSJFX3Vuc2VlbiIsIHBhcnNlPVRSVUUKICAgICAgICAgICAsY29sb3I9ImJsYWNrIikrCmFubm90YXRlKCJzZWdtZW50IiwgeCA9IDYuNiwgeGVuZCA9IDcsIHkgPSAwLjk1LCB5ZW5kID0gMC45NSwKICAgICAgICAgY29sb3VyID0gImJsYWNrIikKcAoKYGBgCgoKLSBJdCAgY2xlYXIgdGhhdCB3aGVuICRrPTkkIG9yICRrPTgkIHRoZXJlIGlzIG92ZXItZml0dGluZyBhbmQgd2hlbiAkaz0wLDEsMiQgdGhlcmUgaXMgdW5kZXItZml0dGluZy4gCgotIEluIHByYWN0aWNlIHBsb3RzIGNhbm5vdCBiZSBwcm9kdWNlZCBiZWNhdXNlIHdlIGRvIG5vdCBrbm93ICRQKHgseSkkLiBJbnN0ZWFkIG9uZSBjYW4gcmVzb3J0IHRvIGVzdGltYXRlcyBiYXNlZCBvbiBjcm9zcyB2YWxpZGF0aW9uIHRvIG9idGFpbiBjdXJ2ZXMgc2ltaWxhciB0byB0aGUgYmxhY2sgIGN1cnZlIAoKCi0gQmVoYXZpb3VyIG9mICoqZXhwZWN0ZWQgZ2VuZXJhbGl6YXRpb24gcGVyZm9ybWFuY2UqKiBhbmQgKipleHBlY3RlZCB0cmFpbmluZyBwZXJmb3JtYW5jZSAqKgoKIVtdKE1vZGVsX2NvbXBsZXhpdHkucG5nKQoKCiMjIEJpYXMgYW5kIFZhcmlhbmNlIERlY29tcG9zaXRpb24KCi0gKipiaWFzIGFuZCB2YXJpYW5jZSB0cmFkZW9mZioqLgoKLSBTcGVjaWFsIGNhc2Ugb2YgdGhlICoqc3F1YXJlIGVycm9yIHBlcmZvcm1hbmNlKiogZnVuY3Rpb24gJHtcY2FsIFB9KFxoYXR7eX0sIHkpID0gKFxoYXR7eX0gLSB5KV4yJCBhbmQgYSBzcGVjaWZpY2FsbHkgYXNzdW1lZCB1bmRlcmx5aW5nIHJhbmRvbSByZWFsaXR5CgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTpwcm9jZXNzLXJlYWx9Cnk9IGYoeCkgKyBcZXBzaWxvbiwgClxxdWFkClx0ZXh0e3dpdGh9ClxxdWFkClx0ZXh0cm17RX1bXGVwc2lsb25dPTAsClxxdWFkClx0ZXh0e2FuZCB9XGVwc2lsb25cdGV4dHsgaXMgaW5kZXBlbmRlbnQgb2YgfXguClxlbmR7ZXF1YXRpb259CgotICAkeCQgYSB2ZWN0b3Igb2YgZmVhdHVyZXMgYW5kICR5JCBhIHNjYWxhciByZWFsIHZhbHVlZCBsYWJlbC4gCgotIEZvciBzb21lIHVuc2VlbiBmZWF0dXJlIHZlY3RvciAkeF5cc3RhciQsIHRoZSBwcmVkaWN0b3IgdHJhaW5lZCBvbiBkYXRhICRcbWF0aGNhbCBEJCBpcyAkXHdpZGVoYXR7eX0oeF5cc3RhciBcLCA7XCwgXG1hdGhjYWwgRCkkLCB3aGljaCB3ZSBhbHNvIGRlbm90ZSB2aWEgJFxoYXR7Zn0oeF5cc3RhciBcLCA7IFwsIFxtYXRoY2FsIEQpJCAKCi0gVGhlICoqZXhwZWN0ZWQgZ2VuZXJhbGl6YXRpb24gcGVyZm9ybWFuY2UqKiAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmUtdW5zZWVuLW9uLXdheX0KXHdpZGV0aWxkZXtFfV97XHRleHR7dW5zZWVufX0gID17XG1hdGhiYiBFfV97XG1hdGhjYWwgRCwgeF5cc3RhciwgXGVwc2lsb259IFxCaWdbIFxiaWcoXGhhdHtmfSh4XlxzdGFyO1xtYXRoY2FsIEQpLShmKHheXHN0YXIpK1xlcHNpbG9uKSBcYmlnKV4yXEJpZ10uClxlbmR7ZXF1YXRpb259CgotIFRoaXMgY2FuIGJlIGV4cHJlc3NlZCBhcyBhICoqYmlhcy12YXJpYW5jZS1ub2lzZSBkZWNvbXBvc2l0aW9uIGVxdWF0aW9uKiosCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTpiaWFzVmFyVHJhZH0KXHdpZGV0aWxkZXtFfV97XHRleHR7dW5zZWVufX09XHVuZGVyYnJhY2V7XGxlZnQoe1xtYXRoYmIgRX1bXGhhdHtmfSh4XlxzdGFyXCwgOyBcLCBcbWF0aGNhbCBEKV0te1xtYXRoYmIgRX1bZih4XlxzdGFyKV1ccmlnaHQpXnsyfX1fe1x0ZXh0e0JpYXMgc3F1YXJlZCBvZn59IFxoYXR7Zn0oXGNkb3QpfQp+K35+Clx1bmRlcmJyYWNle1x0ZXh0e1Zhcn0gXGJpZyhcaGF0e2Z9KHheXHN0YXJcLCA7IFwsIFxtYXRoY2FsIEQpXGJpZyl9X3tcdGV4dHtWYXJpYW5jZSBvZn1+XGhhdHtmfShcY2RvdCl9IAp+fn4rfgogXHVuZGVyYnJhY2V7e1xtYXRoYmIgRX1bXGVwc2lsb25eMl19X3tcdGV4dHtJbmhlcmVudCBOb2lzZX19LgpcZW5ke2VxdWF0aW9ufQoKCi0gVGhlIG1vZGVsIGJpYXMgaXMgYSBtZWFzdXJlIG9mIGhvdyBhIHR5cGljYWwgIG1vZGVsICRcaGF0e2Z9KFxjZG90IFwsIDsgXCwgXG1hdGhjYWwgRCkkIG1pc3NwZWNpZmllcyB0aGUgY29ycmVjdCByZWxhdGlvbnNoaXAgJHtmfShcY2RvdCkkLiAKCgotIFRoZSBtb2RlbCB2YXJpYW5jZSBpcyBhIG1lYXN1cmUgb2YgdGhlIHZhcmlhYmlsaXR5IG9mIHRoZSBtb2RlbCBjbGFzcyAkXGhhdHtmfShcY2RvdFwsIDsgXCwgXG1hdGhjYWwgRCkkLiAKCi0gTW9kZWwgY2xhc3NlcyB3aXRoIGhpZ2ggbW9kZWwgdmFyaWFuY2UgYXJlIG9mdGVuICoqb3ZlcmZpdCoqICh0byB0aGUgdHJhaW5pbmcgZGF0YSkgYW5kIGRvIG5vdCAqKntnZW5lcmFsaXplICh0byB1bnNlZW4gZGF0YSkgd2VsbC4gCgotIEZvciBleGFtcGxlIGluIGEgKipjbGFzc2lmaWNhdGlvbiBzZXR0aW5nKiogeW91IG1heSBjb21wYXJlIHRoZSBhY2N1cmFjeSBvYnRhaW5lZCBvbiB0aGUgKip0cmFpbmluZyBzZXQqKiB0byB0aGF0IG9idGFpbmVkIG9uICoqYSB2YWxpZGF0aW9uIHNldCoqLiBJZiB0aGVyZSBpcyBhIGhpZ2ggZGlzY3JlcGFuY3kgd2hlcmUgdGhlIHRyYWluaW5nIGFjY3VyYWN5IGlzIG11Y2ggaGlnaGVyIHRoYW4gdGhlIHZhbGlkYXRpb24gYWNjdXJhY3ksIHRoZW4gdGhlcmUgaXMgcHJvYmFibHkgYSB2YXJpYW5jZSBwcm9ibGVtIGluZGljYXRpbmcgdGhhdCB0aGUgbW9kZWwgaXMgKipvdmVyZml0dGluZyoqLiAKCgoKCiMjIEFkZGl0aW9uIG9mIFJlZ3VsYXJpemF0aW9uIFRlcm1zCgoKLSBDb250cm9sICoqbW9kZWwgdmFyaWFuY2UqKiBpcyB0byBpbmR1Y2Ugb3IgZm9yY2UgbW9kZWwgcGFyYW1ldGVycyB0byByZW1haW4gd2l0aGluIHNvbWUgY29uZmluZWQgc3Vic2V0IG9mIHRoZSBwYXJhbWV0ZXIgc3BhY2UuIAoKLSBUaGlzIGlzIGNhbGxlZCAqKnJlZ3VsYXJpemF0aW9uKiouIAoKLSBBIGRlY3JlYXNlcyBpbiBtb2RlbCB2YXJpYW5jZSBtYXkgaW1wbHkgYW4gaW5jcmVhc2Ugb2YgbW9kZWwgYmlhcy4gCgotIEEgY29tbW9uIHdheSB0byBrZWVwIG1vZGVsIHBhcmFtZXRlcnMgYXQgYmF5IGlzIHRvIGF1Z21lbnQgdGhlIG9wdGltaXphdGlvbiBvYmplY3RpdmUgJFxtaW5fe1x0aGV0YX0gQyhcdGhldGEgXCwgOyBcLFxtYXRoY2FsIEQpJCAKd2l0aCBhbiBhZGRpdGlvbmFsIFxkZWZpbmVBbmRJbmRleHtyZWd1bGFyaXphdGlvbiB0ZXJtfSAkUl9cbGFtYmRhKFx0aGV0YSkkLiAKCi0gVGhlIHJldmlzZWQgb2JqZWN0aXZlIGlzIHQKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6cmVndWxhcml6YXRpb259ClxtaW5fe1x0aGV0YX0gfkMoXHRoZXRhIFwsIDsgXCwgXG1hdGhjYWwgRCkgKyBSX1xsYW1iZGEoXHRoZXRhKS4KXGVuZHtlcXVhdGlvbn0KCi0gJFJfXGxhbWJkYShcdGhldGEpJCBkZXBlbmRzIG9uIGEgKipyZWd1bGFyaXphdGlvbiBwYXJhbWV0ZXIqKiAkXGxhbWJkYSQKCi0gVGhpcyAqKmh5cGVyLXBhcmFtZXRlcioqIGFsbG93cyB1cyB0byBvcHRpbWl6ZSB0aGUgYmlhcyBhbmQgdmFyaWFuY2UgdHJhZGVvZmYuIAogCi0gIEEgY29tbW9uIGdlbmVyYWwgcmVndWxhcml6YXRpb24gdGVjaG5pcXVlIGNhbGxlZCAqKmVsYXN0aWMgbmV0KiogaGFzIHJlZ3VsYXJpemF0aW9uIHBhcmFtZXRlciAkXGxhbWJkYSA9IChcbGFtYmRhXzEsIFxsYW1iZGFfMikkIGFuZCwKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmUtbmV0fQpSX1xsYW1iZGEoXHRoZXRhKSA9IFxsYW1iZGFfMSBcfCBcdGhldGEgXHxfMSArICBcbGFtYmRhXzIgXHwgXHRoZXRhXHwgXjIKXHF1YWQKXHRleHR7d2l0aH0KXHF1YWQKXHxcdGhldGFcfF8xID0gXHN1bV97aT0xfV57ZH0gfCBcdGhldGFfaSB8Cn5+Clx0ZXh0e2FuZH0Kfn4KXHxcdGhldGFcfF4yID0gXHN1bV97aT0xfV57ZH0gXHRoZXRhX2leMiwKXGVuZHtlcXVhdGlvbn0KCi0gV2l0aCAkXGxhbWJkYV8xLCBcbGFtYmRhXzIgPSAwJCB0aGUgb3JpZ2luYWwgb2JqZWN0aXZlIGlzIHVubW9kaWZpZWQuIAoKLSBJbiBjb250cmFzdCwgYXMgJFxsYW1iZGFfMSBcdG8gXGluZnR5JCBvciAkXGxhbWJkYV8yIFx0byBcaW5mdHkkIHRoZSBlc3RpbWF0ZXMgJFx0aGV0YV9pIFx0byAwJCBhbmQgYW55IGluZm9ybWF0aW9uIGluIHRoZSBkYXRhICRcbWF0aGNhbCBEJCBpcyBmdWxseSBpZ25vcmVkLiAKCi0gUGFydGljdWxhciBjYXNlcyBvZiBlbGFzdGljIG5ldCBhcmUgdGhlIGNsYXNzaWMgKipyaWRnZSByZWdyZXNzaW9uKio6ICRcbGFtYmRhXzEgPSAwJAoKLSBGb3IgJFxsYW1iZGFfMiA9IDAkIHdlIGhhdmUgdGhlICoqTEFTU08qKiAoYGBsZWFzdCBhYnNvbHV0ZSBzaHJpbmthZ2UgYW5kIHNlbGVjdGlvbiBvcGVyYXRvcmBgKQoKLSAgV2l0aCBMQVNTTywgdGhlICBwZW5hbHR5ICR8fCBcdGhldGEgfHxfMSQgIGFsbG93cyB0aGUgYWxnb3JpdGhtIHRvIHJlbW92ZSB2YXJpYWJsZXMgZnJvbSB0aGUgbW9kZWwKCi0gSGVuY2UgTEFTU08gaXMgdmVyeSB1c2VmdWwgYXMgYSBtb2RlbCBzZWxlY3Rpb24gdGVjaG5pcXVlLiAKCgotIFRoZSByZWd1bGFyaXphdGlvbiBwYXJhbWV0ZXIgJFxsYW1iZGEkIGlzICBhIGh5cGVyLXBhcmFtZXRlciB0aGF0IG9uZSB3b3VsZCBsaWtlIHRvIGNhbGlicmF0ZSBkdXJpbmcgbGVhcm5pbmcuIAoKCmBgYHtyLGNhY2hlPVRSVUV9CmxvYWQoIkJyZWFzdF9jYW5jZXIuUkRhdGEiKQpsaWJyYXJ5KGdsbW5ldCkKZGF0YSA8LSBCcmVhc3RfY2FuY2VyX2RhdGEKZGF0YSA8LSBkYXRhICU+JSBtdXRhdGUoZGlhZ25vc2lzXzBfMSA9IGlmZWxzZShkaWFnbm9zaXMgPT0gIk0iLCAxLCAwKSkKbGlicmFyeShjYXJldCkKc2V0LnNlZWQoMTAxKQp0cmFpbmluZyA8LSBjcmVhdGVEYXRhUGFydGl0aW9uKGRhdGEkZGlhZ25vc2lzXzBfMSwgcD0wLjgsIGxpc3Q9RkFMU0UpCnRyYWluIDwtIGRhdGFbIHRyYWluaW5nLCBdCnRlc3QgPC0gZGF0YVsgLXRyYWluaW5nLCBdCnRyYWluZnVsbCA8LSB0cmFpblssLWMoMSwyKV0KdGVzdGZ1bGwgPC0gZGF0YVsgLXRyYWluaW5nLCAtYygxLDIpXQptb2RlbC5sYXNzbyA8LSBnbG1uZXQodHJhaW5mdWxsWywtMzFdLHRyYWluZnVsbFssMzFdLGZhbWlseT0iYmlub21pYWwiLGFscGhhPTEpCm1vZGVsLnJpZGdlIDwtIGdsbW5ldCh0cmFpbmZ1bGxbLC0zMV0sdHJhaW5mdWxsWywzMV0sZmFtaWx5PSJiaW5vbWlhbCIsYWxwaGE9MCkKcGFyKG1mcm93PWMoMiwyKSkKcGxvdChtb2RlbC5yaWRnZSx4dmFyPSJsYW1iZGEiKQpwbG90KG1vZGVsLmxhc3NvLHh2YXI9ImxhbWJkYSIpCnBsb3QobW9kZWwucmlkZ2UseHZhcj0iZGV2IikKcGxvdChtb2RlbC5sYXNzbyx4dmFyPSJkZXYiKQpgYGAKCi0gV2UgcGljayBhIGxhbWJkYSAKCmBgYHtyfQppbmQubGFtYmRhLnIgPC0gd2hpY2gubWluKG1vZGVsLnJpZGdlJGRldi5yYXRpbzwwLjgpCiNtb2RlbC5yaWRnZSRiZXRhWyxpbmQubGFtYmRhLnJdCmluZC5sYW1iZGEubCA8LSB3aGljaC5taW4obW9kZWwubGFzc28kZGV2LnJhdGlvPDAuOCkKI21vZGVsLmxhc3NvJGJldGFbLGluZC5sYW1iZGEubF0KcmVzIDwtIGNiaW5kKG1vZGVsLnJpZGdlJGJldGFbLGluZC5sYW1iZGEucl0sbW9kZWwubGFzc28kYmV0YVssaW5kLmxhbWJkYS5sXSkKY29sbmFtZXMocmVzKSA8LSBjKCJyaWRnZSIsImxhc3NvIikKcmVzCmBgYAoKCiMjIEh5cGVyLXBhcmFtZXRlciBDYWxpYnJhdGlvbiBhbmQgQ3Jvc3MgVmFsaWRhdGlvbiAgCgotIFdBUk5JTkc6IGNhbGlicmF0aW5nIHRoZSBtb2RlbCBjaG9pY2UgYW5kIHRoZSBoeXBlci1wYXJhbWV0ZXJzIHdoaWxlIHJldXNpbmcgdGhlIHRlc3Rpbmcgc2V0IGZvciBwZXJmb3JtYW5jZSBldmFsdWF0aW9uIGlzIGJhZCBwcmFjdGljZSAhISEKCi0gRm9yIHRoaXMgcmVhc29uIGl0IGlzIGNvbW1vbiB0byBmdXJ0aGVyIHNwbGl0IHRoZSB0cmFpbmluZyBkYXRhICRcbWF0aGNhbCBEX3tcdGV4dHt0cmFpbn19JAoKLSAkXG1hdGhjYWwgRF97XHRleHR7dGVzdH19JCBpcyBzdGlsbCByZXNlcnZlZCBvbmx5IGZvciBmaW5hbCBwZXJmb3JtYW5jZSBldmFsdWF0aW9uIGJlZm9yZSByb2xsaW5nIG91dCB0aGUgbW9kZWwgdG8gcHJvZHVjdGlvbi4gCgotIFR3byBtYWluIGFwcHJvYWNoZXMsIHRoZSAqKnRyYWluLXZhbGlkYXRlIHNwbGl0KiogYXBwcm9hY2ggYW5kICoqSy1mb2xkIGNyb3NzIHZhbGlkYXRpb24qKi4gCgotIFRoZSB0cmFpbi12YWxpZGF0ZSBzcGxpdCBhcHByb2FjaCBpcyBjb21tb24gaW4gc2l0dWF0aW9ucyB3aGVyZSB0aGUgdG90YWwgbnVtYmVyIG9mIGRhdGFwb2ludHMgJG4kIGlzIGxhcmdlLiAKCi0gVGhlIEstZm9sZCBjcm9zcyB2YWxpZGF0aW9uIGFwcHJvYWNoIGlzIHVzZWZ1bCB3aGVuIGRhdGEgaXMgbGltaXRlZC4gCgotIFRoZSAqKnRyYWluLXZhbGlkYXRlIHNwbGl0KiogIGltcGxpZXMgdGhhdCB0aGUgb3JpZ2luYWwgZGF0YSB3aXRoICRuJCBzYW1wbGVzIGlzIGZpcnN0IHNwbGl0IHRvIHRyYWluaW5nIGFuZCB0ZXN0aW5nLiAgVGhlbiB0aGUgdHJhaW5pbmcgZGF0YSBpcyBmdXJ0aGVyICoqc3BsaXQgaW50byB0d28gc3Vic2V0cyoqOiAgdGhlIGZpcnN0IGlzIChjb25mdXNpbmdseSkgYWdhaW4gY2FsbGVkIHRoZSAqKnRyYWluaW5nIHNldCoqIGFuZCB0aGUgbGF0dGVyIGlzIHRoZSAqKnZhbGlkYXRpb24gc2V0KiouCgpcWwpcbWF0aGNhbCBEID0gXG1hdGhjYWwgRF97XHRleHR7dHJhaW59fSBcY3VwIFxtYXRoY2FsIERfe1x0ZXh0e3ZhbGlkYXRlfX0gIFxjdXAgXG1hdGhjYWwgRF97XHRleHR7dGVzdH19LApccXVhZApcdGV4dHt3aGVyZSB0aGUgdW5pb25zIGFyZSBvZiBkaXNqb2ludCBzZXRzLn0KXF0KCi0gRm9yIGV4YW1wbGUsIHdlIHVzZSBhIDgwLTIwIHJ1bGUgZm9yIGJvdGggc3BsaXRzIGFuZCBhc3N1bWluZyBkaXZpc2liaWxpdHkgaG9sZHMsIHRoZW4gJG5fe1x0ZXh0e3Rlc3R9fSA9IDAuMiBcdGltZXMgbiQsICRuX3tcdGV4dHt0cmFpbn19ID0gMC42NCBcdGltZXMgbiQgIGFuZCAkbl97XHRleHR7dmFsaWRhdGlvbn19ID0gMC4xNiBcdGltZXMgbiQuIAoKLSBBbHRlcm5hdGl2ZSBhcHByb2FjaCBpcyBLLWZvbGQgY3Jvc3MgdmFsaWRhdGlvbi4KCiFbXShDVi5wbmcpCgoKCi0gUHJhY3RpY2UgZm9yIGBgbGFzc29gYCBhbmQgYGByaWRnZWBgIG1vZGVscwoKYGBge3J9CiMjIEV4YW1wbGUgTGFzc28gYW5kIHJpZGdlIHJlZ3Jlc3Npb24gCiMjIEJyZWFzdCBjYW5jZXIgCiMjIyBBIHByYWN0aWNlIG9uIEJyZWFzdCBDYW5jZXIgRGF0YQptb2RlbC5sYXNzbyA8LSBjdi5nbG1uZXQoYXMubWF0cml4KHRyYWluZnVsbFssLTMxXSksdHJhaW5mdWxsWywzMV0sZmFtaWx5PSJiaW5vbWlhbCIsYWxwaGE9MSx0eXBlLm1lYXN1cmUgPSAiY2xhc3MiKQptb2RlbC5yaWRnZSA8LSBjdi5nbG1uZXQoYXMubWF0cml4KHRyYWluZnVsbFssLTMxXSksdHJhaW5mdWxsWywzMV0sZmFtaWx5PSJiaW5vbWlhbCIsYWxwaGE9MCx0eXBlLm1lYXN1cmUgPSAiY2xhc3MiKQpwbG90KG1vZGVsLmxhc3NvKQpgYGAKCi0gRXZhbHVhdGUgYGBiZXN0IG1vZGVsYGAgb24gdGVzdCBkYXRhCgpgYGB7cn0KcmVzLmwgPC0gcHJlZGljdChtb2RlbC5sYXNzbyxzID0gImxhbWJkYS5taW4iLG5ld3g9YXMubWF0cml4KHRlc3RmdWxsWywtMzFdKSx0eXBlPSJyZXNwb25zZSIpCmNsYXNzaWZpZXIubCA8LSBpZmVsc2UocmVzLmw+MC41LCIxIiwiMCIpCnRhYmxlKGNsYXNzaWZpZXIubCx0ZXN0ZnVsbFssMzFdKQpyZXN1bHQubGFzc28gPC0gY2FyZXQ6OmNvbmZ1c2lvbk1hdHJpeChmYWN0b3IoY2xhc3NpZmllci5sKSxmYWN0b3IodGVzdGZ1bGxbLDMxXSkscG9zaXRpdmU9IjEiKQpyZXN1bHQubGFzc28kdGFibGUKcmVzdWx0Lmxhc3NvJG92ZXJhbGxbMV0KcmVzdWx0Lmxhc3NvJGJ5Q2xhc3NbYygxLDIsNSw2KV0KYGBgCgoKIyMgTXVsdGktY2xhc3MgUHJvYmxlbXMgd2l0aCBTb2Z0bWF4CgotICoqbXVsdGlub21pYWwgcmVncmVzc2lvbiBtb2RlbCoqLCAqKnNvZnRtYXggcmVncmVzc2lvbioqLCAgKipzb2Z0bWF4IGxvZ2lzdGljIHJlZ3Jlc3Npb24qKiwgKiptdWx0aW5vbWlhbCBsb2dpc3RpYyByZWdyZXNzaW9uKiosICoqbXVsdGktY2xhc3MgbG9naXN0aWMgcmVncmVzc2lvbioqIGdlbmVyYWxpemUgKipzaWdtb2lkKiogKGxvZ2lzdGljIG1vZGVsKSBmcm9tIGJpbmFyeSByZXNwb25zZSBjYXNlIHRvIHRoZSBjYXNlIG9mICRLPjIkIGNsYXNzZXMuCgotICAkXG1hdGhjYWwgRD1cbGVmdFx7KHheeygxKX0seV57KDEpfSksXGxkb3RzLCh4Xnsobil9LHleeyhuKX0pXHJpZ2h0XH0kIHdpdGggZWFjaCBsYWJlbCAkeV57KGopfSQgaXMgb25lIG9mICRLJCBjbGFzcyB2YWx1ZXMgJFx7MSxcbGRvdHMsS1x9JC4gCgotIEFpbTogKipwcmVkaWN0KiogY2xhc3MgcHJvYmFiaWxpdHkgdmVjdG9ycywgb3IgaWYgdXNlZCBmb3IgY2xhc3NpZmljYXRpb24sIHRvIHByZWRpY3QgYSBjbGFzcyBpbiBhIG11bHRpLWNsYXNzIHNldHRpbmcuCgotIFRoZSBwcmVkaWN0ZWQgcmVzcG9uc2UgaXMgdGhlIHByb2JhYmlsaXR5IHZlY3RvciAKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6Ym9sZC1waGktcGhpLXh9Clxib2xkc3ltYm9se1xwaGl9KHgpPVxiaWcoXHBoaV8xKHgpLCBcbGRvdHMsIFxwaGlfSyh4KSBcYmlnKSwKXGVuZHtlcXVhdGlvbn0KCndoZXJlClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOnBoaS1tdWx0LWNhc2V9ClxwaGlfayh4KSA9IFAoWSA9IGsgfnx+IFg9eCkKXHF1YWQKXHRleHR7Zm9yfQpccXVhZAprPTEsXGxkb3RzLEsuClxlbmR7ZXF1YXRpb259CgotIFN0YXRpc3RpY2FsIHBhcmFtZXRlcml6YXRpb24KXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6c3RhdC1wYXJhbTF9ClxwaGlfayh4KT1cZnJhY3tlXntiX2srd197KGspfV5cdG9wIHh9fXsxK1xzdW1fe2o9MX1ee0stMX0gZV57Yl9qK3dfeyhqKX1eXHRvcCB4fX0gClxxcXVhZCAKXHRleHR7Zm9yfQpccXF1YWQKaz0xLFxsZG90cyxLLTEsClxlbmR7ZXF1YXRpb259CgphbmQgZnVydGhlciwKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6c3RhdC1wYXJhbTJ9ClxwaGlfSyh4KT0xLVxzdW1fe2o9MX1ee0stMX1ccGhpX2ooeCkuClxlbmR7ZXF1YXRpb259CgotIHJlZ3Jlc3Npb24gcGFyYW1ldGVyOgoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6c3Rhci1yZXAtbWluLW11bHQtbW9kZWwtdGhldGF9Clx0aGV0YT0oYl8xLFxsZG90cyxiX3tLLTF9LHdfeygxKX0sXGxkb3RzLHdfeyhLLTEpfSlcaW4gXHVuZGVyYnJhY2V7XFJlXHRpbWVzXGxkb3RzIFx0aW1lc1xSZX1fe0stMX5cdGV4dHt0aW1lc319IFx0aW1lcyAKXHVuZGVyYnJhY2V7XFJlXnBcdGltZXNcbGRvdHNcdGltZXNcUmVecH1fe0stMX5cdGV4dHt0aW1lc319IDo9IFxUaGV0YSwKXGVuZHtlcXVhdGlvbn0KCi0gKipTb2Z0bWF4IEZ1bmN0aW9uKiogZGVmaW5lcyBmb3IgJHogPSAoel8xLFxsZG90cyx6X0spIFxpbiBcUmVeSyQ6IAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6c29mdG1heC1pbi1tdWx0fQpTX3tcdGV4dHtzb2Z0bWF4fX0oeikgPSBcZnJhY3sxfXtcc3VtX3tpPTF9XntLfSBlXnt6X2l9fSAKXGJlZ2lue2JtYXRyaXh9CmVee3pfMX0gXFwKXHZkb3RzXFwKZV57el97S319XFwKXGVuZHtibWF0cml4fS4KXGVuZHtlcXVhdGlvbn0KCi0gRm9yIGFueSB2ZWN0b3IgJHogXGluIFxSZV5LJCwgdGhlIHJlc3VsdCBvZiAkU197XHRleHR7c29mdG1heH19KHopJCBpcyBhIHByb2JhYmlsaXR5IHZlY3RvcgoKLSBOb3cgYXBwbHkgdGhlIHNvZnRtYXggZnVuY3Rpb24gdG8gYSB2ZWN0b3Igb2YgbGVuZ3RoICRLJCB0aGF0IGhhcyAkYl9rICsgd197KGspfV5cdG9wIHgkIGF0IHRoZSAkayR0aCBjb29yZGluYXRlLiAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOnNvZnRlcX0KXGhhdHt5fT1cdW5kZXJicmFjZXtTX3tcdGV4dHtzb2Z0bWF4fX0gXGJpZyhcb3ZlcmJyYWNle2IrVyAgeH1ee3pcaW4gXFJlXkt9XGJpZyl9X3thXGluIFxSZV5LfSwKXGVuZHtlcXVhdGlvbn0KCndoZXJlICRcaGF0e3l9JCBpcyB0aGUgcHJlZGljdGlvbnZlY3RvciBvZiAkXGJvbGRzeW1ib2x7XHBoaX0oeCkkIHdpdGggCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTptdWx0LXBhcmFtcy12ZWMtbWF0fQpiID0KXGxlZnRbClxiZWdpbnttYXRyaXh9CmJfMVxcClx2ZG90c1xcCmJfSwpcZW5ke21hdHJpeH0KXHJpZ2h0XSwKXHFxdWFkClx0ZXh0e2FuZH0KXHFxdWFkCntXfT0KXGJlZ2lue2JtYXRyaXh9Cn5cdGV4dHstLS0tLS19ICYgd197KDEpfV5cdG9wICYgXHRleHR7LS0tLS0tfSBcXFs1cHRdCn5cdGV4dHstLS0tLS19ICYgd197KDIpfV5cdG9wICYgXHRleHR7LS0tLS0tfSBcXFs1cHRdCiAmIFx2ZG90cyAmIFxcWzVwdF0Kflx0ZXh0ey0tLS0tLX0gJiB3X3soSyl9Xlx0b3AgJiBcdGV4dHstLS0tLS19XFwKXGVuZHtibWF0cml4fS4KXGVuZHtlcXVhdGlvbn0KCi0gKipTb2Z0bWF4IG1vZGVsKiovKipNdWx0aW5vbWlhbCBSZWdyZXNzaW9uKiogaXMgYSAgU2hhbGxvdyBOZXVyYWwgTmV0d29yawoKIVtdKHNvZnRtYXgucG5nKQotICoqQ2xhc3NpZmllcioqOiBhbiBvdXRwdXQgdmVjdG9yICRcaGF0e3l9JCBpcyBhIHByb2JhYmlsaXR5IHZlY3Rvci4gCgotIENob29zZSB0aGUgY2xhc3MgdGhhdCBoYXMgdGhlIGhpZ2hlc3QgcHJvYmFiaWxpdHkgCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTphcmdtYXgtbXB9Clx3aWRlaGF0e1xjYWwgWX09XHVuZGVyc2V0e2sgXGluXHsxLCBcbGRvdHMsIEtcfX17XG9wZXJhdG9ybmFtZXthcmdtYXh9fSB+XGhhdHt5fV9rLgpcZW5ke2VxdWF0aW9ufQoKLSBBIHByYWN0aWNlIG9uIE1OSVNUIGRhdGEgKG9ubHkgb24gNTAwMCBpbWFnZXMpCgpgYGB7cixjYWNoZT1UUlVFfQpsaWJyYXJ5KGdsbW5ldCkKWXRyYWluW3doaWNoKFl0cmFpbj09LTEpXSA8LSAwCmZpdD1jdi5nbG1uZXQoWHRyYWluWzE6MTAwMCxdLFl0cmFpblsxOjEwMDAsXSxmYW1pbHkgPSAibXVsdGlub21pYWwiLHR5cGUubWVhc3VyZSA9ICJjbGFzcyIpCnBsb3QoZml0KQpgYGAKCi0gRXZhbHVhdGUgY2xhc3NpZmllciBvbiB0ZXN0IGRhdGEKCmBgYHtyLG1lc3NhZ2U9TkF9CmxpYnJhcnkoSU1JRkEpCnByZWQ9cHJlZGljdChmaXQsWHRlc3Qscz1maXQkbGFtYmRhLm1pbix0eXBlPSJjbGFzcyIpLTEKcGFyKG1mcm93PWMoMiwzKSkKZm9yKGkgaW4gMTo2KXsKICBzaG93X2RpZ2l0KFh0ZXN0W2ksXSkKICB0aXRsZShzcHJpbnRmKCJwcmVkaWN0aW9uID0gJXMiLHByZWRbaV0pKQp9Cm1lYW4obGFiZWxzX3Rlc3Rfc2V0PT1wcmVkKQpgYGAKLSBJbXByb3ZlIHVzaW5nIG1vcmUgaW1hZ2VzCgpgYGB7cixjYWNoZT1UUlVFfQpsaWJyYXJ5KG5uZXQpCm1vZGVsIDwtIG11bHRpbm9tKFl0cmFpblsxOjIwMDAwLF0gfi4sIGZhbWlseSA9ICJtdWx0aW5vbWlhbCIsIE1heE5XdHMgPTEwMDAwMDAwLCBtYXhpdD01MCxkYXRhPWFzLmRhdGEuZnJhbWUoWHRyYWluWzE6MjAwMDAsXSkpOwpgYGAKCgpgYGB7cn0KcmVzdWx0cyA8LSBwcmVkaWN0KG1vZGVsLCBuZXdkYXRhPVh0ZXN0LCB0eXBlPSdwcm9icycpCnByZWRpY3Rpb24gPC0gbWF4LmNvbChyZXN1bHRzKQpwcmVkaWN0aW9uIDwtIHByZWRpY3Rpb24gLSAxCmNsIDwtIG1lYW4ocHJlZGljdGlvbiAhPSBsYWJlbHNfdGVzdF9zZXQpCnByaW50KHBhc3RlKCdBY2N1cmFjeScsIDEgLSBjbCkpCmBgYAoKCgojIyBCZXlvbmQgbGluZWFyIGJ1bmRhcnkgZGVjaXNpb24KCi0gQmFjayB0byB0aGUgY2FzZSAkaz0yJCB3aXRoIGEgc2lnbW9pZCBtb2RlbAoKLSBDb25zaWRlciBhIHNjZW5hcmlvIHdpdGggJHA9MiQgZmVhdHVyZXMgCgpgYGB7cn0KbG9hZCgidmVyc2F0aWxlLWJvdW5kYXJpZXMuUkRhdGEiKQpsaWJyYXJ5KGdncGxvdDIpCmdncGxvdChkYXRhKSArIGdlb21fcG9pbnQoYWVzKHggPSB4LHkgPSB5LGNvbG9yID0gYXMuY2hhcmFjdGVyKGxhYmVsKSksIHNpemUgPSAxKSArCiAgdGhlbWVfYncoYmFzZV9zaXplID0gMTUpICsKICB4bGltKC0yLjUsIDEuNSkgKwogIHlsaW0oLTIuNSwgMi41KSArCiAgY29vcmRfZml4ZWQocmF0aW8gPSAwLjgpICsKICB0aGVtZShheGlzLnRpY2tzPWVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBwYW5lbC5ncmlkLm1ham9yID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIHBhbmVsLmdyaWQubWlub3IgPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50ZXh0PWVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLnRpdGxlPWVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCmBgYAoKLSBXZSBmaXJzdCB1c2UgYSAqKnNpZ21vaWQqKiBtb2RlbCBhbmQgY2hlY2sgdGhlIGRlY2lzaW9uIGJvdW5kYXJ5CgpgYGB7cn0KdHJhaW5fZGF0YSA8LSBkYXRhCnRyYWluWCA8LSB0cmFpbl9kYXRhWywgYygxLCAyKV0KdHJhaW5ZIDwtIHRyYWluX2RhdGFbLCAzXQp0cmFpblkgPC0gaWZlbHNlKHRyYWluWSA9PSAxLCAwLCAxKQpkYXRhLmdsbSA8LSBkYXRhLmZyYW1lKFk9dHJhaW5ZLFgxPXRyYWluWFssMV0sWDI9dHJhaW5YWywyXSkKbW9kZWwubG9naXN0aWMgPC0gZ2xtKFl+WDErWDIsZGF0YT1kYXRhLmdsbSxmYW1pbHk9Ymlub21pYWwpCiMjIEFzIGEgcmVtaW5kZXIgd2UgY2hlY2sgdGhlIHNoYXBlIG9mIG91ciBjbGFzc2lmaWVyCnN0ZXAgPC0gMC4wMQp4X21pbiA8LSBtaW4odHJhaW5YWywgMV0pIC0gMC4yCnhfbWF4IDwtIG1heCh0cmFpblhbLCAxXSkgKyAwLjIKeV9taW4gPC0gbWluKHRyYWluWFssIDJdKSAtIDAuMgp5X21heCA8LSBtYXgodHJhaW5YWywgMl0pICsgMC4yCmdyaWQgPC0gYXMubWF0cml4KGV4cGFuZC5ncmlkKHNlcSh4X21pbiwgeF9tYXgsIGJ5ID0gc3RlcCksIHNlcSh5X21pbiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHlfbWF4LCBieSA9IHN0ZXApKSkKCmRhdGEuZ3JpZCA8LSBkYXRhLmZyYW1lKFgxPWdyaWRbLDFdLFgyPWdyaWRbLDJdKQoKWiA8LSBwcmVkaWN0KG1vZGVsLmxvZ2lzdGljLG5ld2RhdGE9ZGF0YS5ncmlkLHR5cGU9InJlc3BvbnNlIikKWiA8LSBpZmVsc2UoWiA8MC41LCAxLCAyKQoKCmcxIDwtIGdncGxvdCgpICsKICBnZW9tX3RpbGUoYWVzKHggPSBncmlkWywgMV0sIHkgPSBncmlkWywgMl0sIGZpbGwgPSBhcy5jaGFyYWN0ZXIoWikpLCBhbHBoYSA9IDAuMywgc2hvdy5sZWdlbmQgPSBGKSsKICBnZW9tX3BvaW50KGRhdGEgPSB0cmFpbl9kYXRhLCBhZXMoeCA9IHgsIHkgPSB5LCBjb2xvciA9IGFzLmNoYXJhY3Rlcih0cmFpblkpKSxzaXplID0gMSkrCiAgdGhlbWVfYncoYmFzZV9zaXplID0gMTUpICsgY29vcmRfZml4ZWQocmF0aW8gPSAwLjgpICsKICBsYWJzKHg9ZXhwcmVzc2lvbih4WzFdKSxjZXg9MikgK2xhYnMoeT1leHByZXNzaW9uKHhbMl0pKSsKICB0aGVtZShheGlzLnRpY2tzID0gZWxlbWVudF9ibGFuaygpLCBwYW5lbC5ncmlkLm1ham9yID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgcGFuZWwuZ3JpZC5taW5vciA9IGVsZW1lbnRfYmxhbmsoKSwgbGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiLGF4aXMudGl0bGU9ZWxlbWVudF90ZXh0KHNpemU9MTgsZmFjZT0iaXRhbGljIikpCiAgCmcxCmBgYAoKLSBJdCBpcyBhIGJhZCBsaW5lYXIgY2xhc3NpZmllcjoKClxbIFBbWT0xfFhfMT14XzEsWF8yPXhfMl09XGZyYWN7MX17MStlXnstKGIrd18xeF8xK3dfMnhfMil9fSBcXSAKCi0gV2UgY2FuIHVzZSBwb2x5bm9taWFsIGZlYXR1cmUgZW5naW5lZXJpbmc6CgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTpxdWFkLWRlY2lzaW9uLWJvdW5kcnl9Clx0aWxkZXtifSArIFx0aWxkZXt3fV8xIHhfMSArIFx0aWxkZXt3fV8yIHhfMiArIFx0aWxkZXt3fV8zIHhfMV4yICArIFx0aWxkZXt3fV80IHhfMl4yICArIFx0aWxkZXt3fV81IHhfMSB4XzIgXGdlIDAuClxlbmR7ZXF1YXRpb259CgotIEZlYXR1cmUgZW5naW5lZXJpbmcgYWxsb3dzIGZvciBub24gbGluZWFyIGRlY2lzaW9uIGJvdW5kYXJpZXMuCgoKYGBge3J9Cm1vZGVsLmxvZ2lzdGljLm5sMiA8LSBnbG0oWX5wb2x5bShYMSwgWDIsIGRlZ3JlZT0yLCByYXc9VFJVRSksZGF0YT1kYXRhLmdsbSxmYW1pbHk9Ymlub21pYWwpCgoKWiA8LSBwcmVkaWN0KG1vZGVsLmxvZ2lzdGljLm5sMixuZXdkYXRhPWRhdGEuZ3JpZCx0eXBlPSJyZXNwb25zZSIpClogPC0gaWZlbHNlKFogPDAuNSwgMSwgMikKCmcyIDwtIGdncGxvdCgpICsKICBnZW9tX3RpbGUoYWVzKHggPSBncmlkWywgMV0sIHkgPSBncmlkWywgMl0sIGZpbGwgPSBhcy5jaGFyYWN0ZXIoWikpLCBhbHBoYSA9IDAuMywgc2hvdy5sZWdlbmQgPSBGKSsKICBnZW9tX3BvaW50KGRhdGEgPSB0cmFpbl9kYXRhLCBhZXMoeCA9IHgsIHkgPSB5LCBjb2xvciA9IGFzLmNoYXJhY3Rlcih0cmFpblkpKSxzaXplID0gMSkrCiAgdGhlbWVfYncoYmFzZV9zaXplID0gMTUpICsgY29vcmRfZml4ZWQocmF0aW8gPSAwLjgpICsKICB0aGVtZShheGlzLnRpY2tzID0gZWxlbWVudF9ibGFuaygpLCBwYW5lbC5ncmlkLm1ham9yID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIHBhbmVsLmdyaWQubWlub3IgPSBlbGVtZW50X2JsYW5rKCksIGF4aXMudGV4dCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLnRpdGxlID0gZWxlbWVudF9ibGFuaygpLCBsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpKwogIHRoZW1lKGF4aXMudGl0bGU9ZWxlbWVudF90ZXh0KHNpemU9MTgsZmFjZT0iaXRhbGljIikpCgpnMisgbGFicyh4PWV4cHJlc3Npb24oeFsxXSksY2V4PTIpICtsYWJzKHk9ZXhwcmVzc2lvbih4WzJdKSxjZXg9MikKYGBgCi0gSW52ZXN0aWdhdGUgaGlnaGVyIG9yZGVyIAoKCmBgYHtyfQptb2RlbC5sb2dpc3RpYy5ubDMgPC0gZ2xtKFl+cG9seW0oWDEsIFgyLCBkZWdyZWU9NCwgcmF3PVRSVUUpLGRhdGE9ZGF0YS5nbG0sZmFtaWx5PWJpbm9taWFsKQptb2RlbC5sb2dpc3RpYy5ubDQgPC0gZ2xtKFl+cG9seW0oWDEsIFgyLCBkZWdyZWU9OCwgcmF3PVRSVUUpLGRhdGE9ZGF0YS5nbG0sZmFtaWx5PWJpbm9taWFsKQoKWiA8LSBwcmVkaWN0KG1vZGVsLmxvZ2lzdGljLm5sMyxuZXdkYXRhPWRhdGEuZ3JpZCx0eXBlPSJyZXNwb25zZSIpClogPC0gaWZlbHNlKFogPDAuNSwgMSwgMikKcGFyKG1mcm93PWMoMSwyKSkKZzIgPC0gZ2dwbG90KCkgKwogIGdlb21fdGlsZShhZXMoeCA9IGdyaWRbLCAxXSwgeSA9IGdyaWRbLCAyXSwgZmlsbCA9IGFzLmNoYXJhY3RlcihaKSksIGFscGhhID0gMC4zLCBzaG93LmxlZ2VuZCA9IEYpKwogIGdlb21fcG9pbnQoZGF0YSA9IHRyYWluX2RhdGEsIGFlcyh4ID0geCwgeSA9IHksIGNvbG9yID0gYXMuY2hhcmFjdGVyKHRyYWluWSkpLHNpemUgPSAxKSsKICB0aGVtZV9idyhiYXNlX3NpemUgPSAxNSkgKyBjb29yZF9maXhlZChyYXRpbyA9IDAuOCkgKwogIHRoZW1lKGF4aXMudGlja3MgPSBlbGVtZW50X2JsYW5rKCksIHBhbmVsLmdyaWQubWFqb3IgPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgcGFuZWwuZ3JpZC5taW5vciA9IGVsZW1lbnRfYmxhbmsoKSwgYXhpcy50ZXh0ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGl0bGUgPSBlbGVtZW50X2JsYW5rKCksIGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikrCiAgdGhlbWUoYXhpcy50aXRsZT1lbGVtZW50X3RleHQoc2l6ZT0xOCxmYWNlPSJpdGFsaWMiKSkKCmcyKyBsYWJzKHg9ZXhwcmVzc2lvbih4WzFdKSxjZXg9MikgK2xhYnMoeT1leHByZXNzaW9uKHhbMl0pLGNleD0yKQoKClogPC0gcHJlZGljdChtb2RlbC5sb2dpc3RpYy5ubDQsbmV3ZGF0YT1kYXRhLmdyaWQsdHlwZT0icmVzcG9uc2UiKQpaIDwtIGlmZWxzZShaIDwwLjUsIDEsIDIpCmczIDwtIGdncGxvdCgpICsKICBnZW9tX3RpbGUoYWVzKHggPSBncmlkWywgMV0sIHkgPSBncmlkWywgMl0sIGZpbGwgPSBhcy5jaGFyYWN0ZXIoWikpLCBhbHBoYSA9IDAuMywgc2hvdy5sZWdlbmQgPSBGKSsKICBnZW9tX3BvaW50KGRhdGEgPSB0cmFpbl9kYXRhLCBhZXMoeCA9IHgsIHkgPSB5LCBjb2xvciA9IGFzLmNoYXJhY3Rlcih0cmFpblkpKSxzaXplID0gMSkrCiAgdGhlbWVfYncoYmFzZV9zaXplID0gMTUpICsgY29vcmRfZml4ZWQocmF0aW8gPSAwLjgpICsKICBsYWJzKHg9ZXhwcmVzc2lvbih4WzFdKSxjZXg9MikgK2xhYnMoeT1leHByZXNzaW9uKHhbMl0pKSsKICB0aGVtZShheGlzLnRpY2tzID0gZWxlbWVudF9ibGFuaygpLCBwYW5lbC5ncmlkLm1ham9yID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIHBhbmVsLmdyaWQubWlub3IgPSBlbGVtZW50X2JsYW5rKCksIGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIixheGlzLnRpdGxlPWVsZW1lbnRfdGV4dChzaXplPTE4LGZhY2U9Iml0YWxpYyIpKQoKCmczKyBsYWJzKHg9ZXhwcmVzc2lvbih4WzFdKSxjZXg9MikgK2xhYnMoeT1leHByZXNzaW9uKHhbMl0pLGNleD0yKQpgYGAKCi0gaGlnaGVyIG9yZGVycyBtaWdodCBnYWluIG1vcmUgZXhwcmVzc2l2aXR5IGJ1dCBIaWdoZXIgb3JkZXIgbW9kZWxzIHlpZWxkIG9ic2N1cmUgY2xhc3NpZmljYXRpb24gZGVjaXNpb24gYm91bmRhcmllcy4gCgotIENlcnRhaW5seSBhcHBlYXIgbGlrZSBhbiBvdmVyLWZpdC4gCgotIE5ldyBzZXQgb2YgZmVhdHVyZXMgY291bGQgYmVjb21lIGhpZ2hseSBjb3JyZWxhdGVkIGFuZCB0aGF0IGNhbiBjYXVzZSBkaWZmaWN1bHR5IGluIGluZmVyZW5jZSBvZiBwYXJhbWV0ZXJzLgoKIyMgTXVsdGktY2xhc3MgY2xhc3NpZmljYXRpb246IHN5bnRoZXRpYyBkYXRhIGV4YW1wbGUKCmBgYHtyLGNhY2hlPVRSVUUsbWVzc2FnZT1OQX0KY2xyMSA8LSBjKHJnYigxLDAsMCwxKSxyZ2IoMCwxLDAsMSkscmdiKDAsMCwxLDEpLHJnYigwLjUsMC41LDAuNSwxKSkKY2xyMiA8LSBjKHJnYigxLDAsMCwuMSkscmdiKDAsMSwwLC4xKSxyZ2IoMCwwLDEsLjEpLHJnYigwLjUsMC41LDAuNSwuNSkpCnggPC0gYyguNCwuNTUsLjY1LC45LC4xLC4zNSwuNSwuMTUsLjIsLjg1LDAuMiwwLjcsMC4zLDAuNSwwLjYsMC41NSwwLjQpCnkgPC0gYyguODUsLjk1LC44LC44NywuNSwuNTUsLjUsLjIsLjEsLjMsMC43LDAuNSwwLjMsMC43LDAuNiwwLjY1LDAuNykKeiA8LSBjKDEsMiwyLDIsMSwwLDAsMSwwLDAsMSwyLDEsMywzLDMsMykKZGYgPC0gZGF0YS5mcmFtZSh4LHkseikKcGxvdCh4LHkscGNoPTE5LGNleD0yLGNvbD1jbHIxW3orMV0seWxhYj1leHByZXNzaW9uKHhbMl0pLHhsYWI9ZXhwcmVzc2lvbih4WzFdKSxjZXgubGFiPTEuNCkKI3dyaXRlLmNzdihkZixmaWxlPSJzeW50aGV0aWNfZGF0YV80X2NsYXNzLmNzdiIscm93Lm5hbWVzID0gRkFMU0UpCmxpYnJhcnkobm5ldCkKbW9kZWwubXVsdCA8LSBtdWx0aW5vbSh6fngreSxkYXRhPWRmKQoKcHJlZF9tdWx0IDwtIGZ1bmN0aW9uKHgseSl7CiAgcmVzIDwtIHByZWRpY3QobW9kZWwubXVsdCwKICAgICAgICAgICAgICAgICBuZXdkYXRhPWRhdGEuZnJhbWUoeD14LHk9eSksdHlwZT0icHJvYnMiKQogIGFwcGx5KHJlcyxNQVJHSU49MSx3aGljaC5tYXgpCn0KeF9ncmlkPC1zZXEoMCwxLGxlbmd0aD02MDEpCnlfZ3JpZDwtc2VxKDAsMSxsZW5ndGg9NjAxKQp6X2dyaWQgPC0gb3V0ZXIoeF9ncmlkLHlfZ3JpZCxGVU49cHJlZF9tdWx0KQoKCmltYWdlKHhfZ3JpZCx5X2dyaWQsel9ncmlkLGNvbD1jbHIyLHlsYWI9ZXhwcmVzc2lvbih4WzJdKSx4bGFiPWV4cHJlc3Npb24oeFsxXSksY2V4LmxhYj0xLjQpCgpwb2ludHMoeCx5LHBjaD0xOSxjZXg9Mixjb2w9Y2xyMVt6KzFdKQpsZWdlbmQoInRvcGxlZnQiLCBpbnNldD0wLjAyLCBsZWdlbmQ9YygiY2xhc3MgMSIsICJjbGFzcyAyIiwiY2xhc3MgMyIsImNsYXNzIDQiKSwKICAgICAgIGNvbD1jbHIxW2MoMSwzLDIsNCldLCBjZXg9MC45LCBwY2g9YygxOSwxOSkpCgptb2RlbC5tdWx0IDwtIG11bHRpbm9tKHp+cG9seW0oeCx5LCBkZWdyZWU9MiwgcmF3PVRSVUUpLGRhdGE9ZGYpCgoKeF9ncmlkPC1zZXEoMCwxLGxlbmd0aD02MDEpCnlfZ3JpZDwtc2VxKDAsMSxsZW5ndGg9NjAxKQp6X2dyaWQgPC0gb3V0ZXIoeF9ncmlkLHlfZ3JpZCxGVU49cHJlZF9tdWx0KQoKaW1hZ2UoeF9ncmlkLHlfZ3JpZCx6X2dyaWQsY29sPWNscjIseWxhYj1leHByZXNzaW9uKHhbMl0pLHhsYWI9ZXhwcmVzc2lvbih4WzFdKSxjZXgubGFiPTEuNCkKCnBvaW50cyh4LHkscGNoPTE5LGNleD0yLGNvbD1jbHIxW3orMV0pCmxlZ2VuZCgidG9wbGVmdCIsIGluc2V0PTAuMDIsIGxlZ2VuZD1jKCJjbGFzcyAxIiwgImNsYXNzIDIiLCJjbGFzcyAzIiwiY2xhc3MgNCIpLAogICAgICAgY29sPWNscjFbYygxLDMsMiw0KV0sIGNleD0wLjksIHBjaD1jKDE5LDE5KSkKCgptb2RlbC5tdWx0IDwtIG11bHRpbm9tKHp+cG9seW0oeCx5LCBkZWdyZWU9OCwgcmF3PVRSVUUpLGRhdGE9ZGYpCgoKeF9ncmlkPC1zZXEoMCwxLGxlbmd0aD02MDEpCnlfZ3JpZDwtc2VxKDAsMSxsZW5ndGg9NjAxKQp6X2dyaWQgPC0gb3V0ZXIoeF9ncmlkLHlfZ3JpZCxGVU49cHJlZF9tdWx0KQoKCmltYWdlKHhfZ3JpZCx5X2dyaWQsel9ncmlkLGNvbD1jbHIyLHlsYWI9ZXhwcmVzc2lvbih4WzJdKSx4bGFiPWV4cHJlc3Npb24oeFsxXSksY2V4LmxhYj0xLjQpCgpwb2ludHMoeCx5LHBjaD0xOSxjZXg9Mixjb2w9Y2xyMVt6KzFdKQpsZWdlbmQoInRvcGxlZnQiLCBpbnNldD0wLjAyLCBsZWdlbmQ9YygiY2xhc3MgMSIsICJjbGFzcyAyIiwiY2xhc3MgMyIsImNsYXNzIDQiKSwKICAgICAgIGNvbD1jbHIxW2MoMSwzLDIsNCldLCBjZXg9MC45LCBwY2g9YygxOSwxOSkpCmBgYAoKIyMgT3B0aW1pemF0aW9uIGFuZCBsb3NzIGZ1bmN0aW9uIAoKCi0gTGVhcm5pbmcgYWN0aXZpdHkgaW52b2x2ZXMgb3B0aW1pemF0aW9uIAoKLSBMZWFybmluZyBpcyB0aGUgcHJvY2VzcyBvZiBzZWVraW5nIG1vZGVsIHBhcmFtZXRlcnMgdGhhdCBhcmUgYGBiZXN0JycgZm9yIHNvbWUgZ2l2ZW4gdGFzay4KCi0gYGBMb3NzIGZ1bmN0aW9uYGAgaXMgZ2VuZXJhbGx5IHVzZWQgYXMgYGBwcm94eWBgIGZvciBtaW5pbWl6YXRpb24gb2YgdGhlIGFjdHVhbCBwZXJmb3JtYW5jZSBtZWFzdXJlcyB0aGF0IGFyZSBvZiBpbnRlcmVzdAoKLSBFeGFtcGxlOiBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtcyBhaW0gdG8gZ2V0IHRoZSBtb3N0IGFjY3VyYXRlIGNsYXNzaWZpZXIuIEluIHN1Y2ggYSBjYXNlLCBvcHRpbWl6YXRpb24gaXMgdHlwaWNhbGx5IG5vdCBjYXJyaWVkIG91dCBkaXJlY3RseSBvbiB0aGUgYWNjdXJhY3kgbWVhc3VyZSBidXQgcmF0aGVyIG9uIGEgbG9zcyBmdW5jdGlvbiBzdWNoIGFzIHRoZSBgYG1lYW4gc3F1YXJlIGVycm9yYGAsIG9yIGBgY3Jvc3MgZW50cm9weWBgCgotIEZvciBgYmluYXJ5IG91dGNvbWVgLCB3ZSB1c2UgKipiaW5hcnkgY3Jvc3MgZW50cm9weSoqCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTpiaW4tY3Jvc3MtZW50eX0KXHRleHR7Q0V9X3tcdGV4dHtiaW5hcnl9fSh7eX0sXGhhdHt5fSkgPS0gXEJpZyggeSBcbG9ne1xiaWcoXGhhdHt5fSBcYmlnKX0rKDEteSApXGxvZ3tcYmlnKDEtXGhhdHt5fSBcYmlnKX1cQmlnKSwKXGVuZHtlcXVhdGlvbn0KCi0gRm9yIGBudW1lcmljYWwgb3V0Y29tZWBgLCB3ZSBnZW5lcmFsbHkgdXNlIHRoZSAqKlNxdWFyZSBlcnJvciBsb3NzKioKClxbCkNfaShcdGhldGEpPSh7eX0gLSBcaGF0e3l9KV4yLgpcXQoKLSBGb3IgYGNhdGVnb3JpY2FsIG91dGNvbWVgLCB3ZSBnZW5lcmFsbHkgdXNlIHRoZSAqKmNhdGVnb3JpY2FsIGNyb3NzIGVudHJvcHkqKi4gRm9yIGEgbGFiZWwgJHkgXGluIFx7MSxcbGRvdHMsS1x9JCBhbmQgYSBwcm9iYWJpbGl0eSB2ZWN0b3IgJFxoYXR7eX0kIG9mIGxlbmd0aCAkSyQ6CiUKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6Y2F0LWNyb3NzLWVudHJ9Clx0ZXh0e0NFfV9cdGV4dHtjYXRlZ29yaWNhbH0oeSwgXGhhdHt5fSkgPSAtIFxzdW1fe2s9MX1eSyB7e1xtYXRoYmYgMX1ce3kgPSBrXH19IFxsb2cgXGhhdHt5fV9rClxlbmR7ZXF1YXRpb259CgotIFdoeSBpcyBtYXR0ZXIgdG8gY2hvb3NlIHRoZSBhcHByb3ByaWF0ZSBsb3NzIGZ1bmN0aW9uID8gbG9zcyBsYW5kc2NhcGUgb2YgYGBTaWdtb2lkIG1vZGVsYGAKCgohW10obG9zc19sYW5kc2NhcGUucG5nKQotIChhKSBVc2luZyB0aGUgc3F1YXJlZCBsb3NzICBhbmQgIChiKSBVc2luZyB0aGUgYmluYXJ5IGNyb3NzIGVudHJvcHkgbG9zcyAKCi0gU29tZSBCZW5lZml0cyBvZiBDcm9zcyBFbnRyb3B5IExvc3M6CgogICAgLSB0aGUgY3Jvc3MgZW50cm9weSBsb3NzIGxhbmRzY2FwZSBpcyBtb3JlIG1hbmFnZWFibGUgdG8gbmF2aWdhdGUgZm9yIGFuIG9wdGltaXphdGlvbiBhbGdvcml0aG0gbGlrZSBncmFkaWVudCBkZXNjZW50LgogICAgLSBJbiB0aGUgY2FzZSBvZiBsb2dpc3RpYyByZWdyZXNzaW9uLCBjcm9zcyBlbnRyb3B5IGFsd2F5cyB5aWVsZHMgYSBjb252ZXggbG9zcyBsYW5kc2NhcGUgCiAgICAtIEhlcmUsIHRoZSBzcXVhcmVkIGVycm9yIGxvc3MgIHlpZWxkIG5vbi1jb252ZXggbG9zcyBsYW5kc2NhcGUsLCBtdWx0aXBsZSBsb2NhbCBtaW5pbWEgYXMgd2VsbCBhcyBzYWRkbGUgcG9pbnRzLgoKCi0gT3B0aW1pemF0aW9uIG9mIHRoZSBsb3NzIGZ1bmN0aW9uIHRocm91Z2ggKipHcmFkaWVudCBEZXNjZW50KiogYWxnb3JpdGhtcwoKCgoKIVtdKEdyYWRpZW50X2FsZ28ucG5nKQoKLSBUaGlzICoqZ3JhZGllbnQgZGVzY2VudCoqIHByb2NlZHVyZSBleGVjdXRlcyBvdmVyIGl0ZXJhdGlvbnMgaW5kZXhlZCBieSAkdD0wLDEsMixcbGRvdHMkIAoKLSBXb3JrcyBieSB0YWtpbmcgc21hbGwgc3RlcHMgaW4gdGhlIGRpcmVjdGlvbiBvcHBvc2l0ZSB0byB0aGUgZ3JhZGllbnQuIAoKLSBUaGF0IGlzLCBpdCB0cmF2ZXJzZXMgYGBkb3duaGlsbGBgIGVhY2ggdGltZSB0cnlpbmcgdG8gZGVzY2VuZCBpbiB0aGUgc3RlZXBlc3QgZGlyZWN0aW9uLiAKCi0gU3RlcHMgYXJlIGRldGVybWluZWQgYnkgYSBmaXhlZCAkXGFscGhhID4gMCQgY2FsbGVkIHRoZSAqKmxlYXJuaW5nIHJhdGUqKi4gCgotIEFmdGVyIHNvbWUgaW5pdGlhbGl6YXRpb24gICRcdGhldGFeeygwKX0gPSBcdGhldGFfe2luaXR9JCwgaW4gZWFjaCBpdGVyYXRpb24gJHQkLCB0aGUgbmV4dCAgdmVjdG9yICRcdGhldGFeeyh0KzEpfSQgaXMgb2J0YWluZWQgdmlhLAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6Z2RsczF9Clx0aGV0YV57KHQrMSl9ID0gXHRoZXRhXnsodCl9IC0gXGFscGhhIFxuYWJsYSBDKFx0aGV0YV57KHQpfSkuClxlbmR7ZXF1YXRpb259CgoKLSBFeGFtcGxlOiBsaW5lYXIgbW9kZWwgd2l0aCBhbiBpbnRlcmNlcHQgYW5kIG9uZSBmZWF0dXJlCgohW10oR3JhZGllbnRfZGVzY2VudC5wbmcpCgotIENvbnZlcmdlbmNlIGNhbiBkZXBlbmQgb2YgdGhlIGxlYXJuaW5nIHJhdGUgY2hvaWNlICEhIQoKLSBTdGFuZGFyZGl6YXRpb24gb2YgSW5wdXRzIGNhbiBoZWxwIHRoZSBvcHRpbWl6YXRpb24gCgoKIVtdKG5vcm1hbGl6ZWRfaW5wdXQucG5nKQoKLSBJbGx1c3RyYXRpb24gb2YgZ3JhZGllbnQgZGVzY2VudCBvbiAqKldpc2NvbnNpbiBicmVhc3QgY2FuY2VyIGRhdGFzZXQqKgoKLSBXZSBzcGxpdCBoZSBvYnNlcnZhdGlvbnMgaW50byAkbl97XHRleHR7dHJhaW59fSA9IDQ1NiQgYW5kICRuX3tcdGV4dHt0ZXN0fX09MTEzJC4gCgotIFdlIHVzZSBhIG1vZGVsIHdpdGggJHA9MTAkIGZlYXR1cmVzICgkZD0xMSQpIGFuZCBsZWFybiB0aGUgcGFyYW1ldGVycyB2aWEgZ3JhZGllbnQgZGVzY2VudCB3aXRoIHNvbWUgYXJiaXRyYXJ5IGluaXRpbGl6YXRpb24uCgoKIVtdKGxvc3NfZXhhbXBsZS5wbmcpCg==